1 | /* $Id: hash_code.hpp 3680 2015-05-07 19:17:37Z bradbell $ */ |
---|
2 | # ifndef CPPAD_HASH_CODE_INCLUDED |
---|
3 | # define CPPAD_HASH_CODE_INCLUDED |
---|
4 | |
---|
5 | /* -------------------------------------------------------------------------- |
---|
6 | CppAD: C++ Algorithmic Differentiation: Copyright (C) 2003-15 Bradley M. Bell |
---|
7 | |
---|
8 | CppAD is distributed under multiple licenses. This distribution is under |
---|
9 | the terms of the |
---|
10 | Eclipse Public License Version 1.0. |
---|
11 | |
---|
12 | A copy of this license is included in the COPYING file of this distribution. |
---|
13 | Please visit http://www.coin-or.org/CppAD/ for information on other licenses. |
---|
14 | -------------------------------------------------------------------------- */ |
---|
15 | |
---|
16 | namespace CppAD { // BEGIN_CPPAD_NAMESPACE |
---|
17 | /*! |
---|
18 | \file hash_code.hpp |
---|
19 | CppAD hashing utility. |
---|
20 | */ |
---|
21 | |
---|
22 | /*! |
---|
23 | \def CPPAD_HASH_TABLE_SIZE |
---|
24 | the codes retruned by hash_code are between zero and CPPAD_HASH_TABLE_SIZE |
---|
25 | minus one. |
---|
26 | */ |
---|
27 | # define CPPAD_HASH_TABLE_SIZE 10000 |
---|
28 | |
---|
29 | /*! |
---|
30 | General purpose hash code for an arbitrary value. |
---|
31 | |
---|
32 | \tparam Value |
---|
33 | is the type of the argument being hash coded. |
---|
34 | It should be a plain old data class; i.e., |
---|
35 | the values included in the equality operator in the object and |
---|
36 | not pointed to by the object. |
---|
37 | |
---|
38 | \param value |
---|
39 | the value that we are generating a hash code for. |
---|
40 | |
---|
41 | \return |
---|
42 | is a hash code that is between zero and CPPAD_HASH_TABLE_SIZE - 1. |
---|
43 | |
---|
44 | \par Checked Assertions |
---|
45 | \li \c std::numeric_limits<unsigned short>::max() >= CPPAD_HASH_TABLE_SIZE |
---|
46 | \li \c sizeof(value) is even |
---|
47 | \li \c sizeof(unsigned short) == 2 |
---|
48 | */ |
---|
49 | |
---|
50 | template <class Value> |
---|
51 | unsigned short hash_code(const Value& value) |
---|
52 | { CPPAD_ASSERT_UNKNOWN( |
---|
53 | std::numeric_limits<unsigned short>::max() |
---|
54 | >= |
---|
55 | CPPAD_HASH_TABLE_SIZE |
---|
56 | ); |
---|
57 | CPPAD_ASSERT_UNKNOWN( sizeof(unsigned short) == 2 ); |
---|
58 | CPPAD_ASSERT_UNKNOWN( sizeof(value) % 2 == 0 ); |
---|
59 | # |
---|
60 | const unsigned short* v |
---|
61 | = reinterpret_cast<const unsigned short*>(& value); |
---|
62 | # |
---|
63 | size_t i = sizeof(value) / 2 - 1; |
---|
64 | # |
---|
65 | unsigned short code = v[i]; |
---|
66 | # |
---|
67 | while(i--) |
---|
68 | code += v[i]; |
---|
69 | |
---|
70 | return code % CPPAD_HASH_TABLE_SIZE; |
---|
71 | } |
---|
72 | |
---|
73 | /*! |
---|
74 | Specialized hash code for a CppAD operator and its arguments. |
---|
75 | |
---|
76 | \param op |
---|
77 | is the operator that we are computing a hash code for. |
---|
78 | If it is not one of the following operartors, the operator is not |
---|
79 | hash coded and zero is returned: |
---|
80 | |
---|
81 | \li unary operators: |
---|
82 | AbsOp, AcosOp, AcoshOp, AsinOp, AsinhOp, AtanOp, CosOp, CoshOp |
---|
83 | ExpOp, LogOp, SinOp, SinhOp, SqrtOp, TanOp, TanhOp |
---|
84 | |
---|
85 | \li binary operators where first argument is a parameter: |
---|
86 | AddpvOp, DivpvOp, MulpvOp, PowpvOp, SubpvOp, |
---|
87 | |
---|
88 | \li binary operators where second argument is a parameter: |
---|
89 | DivvpOp, PowvpOp, SubvpOp |
---|
90 | |
---|
91 | \li binary operators where first is an index and second is a variable: |
---|
92 | DisOp |
---|
93 | |
---|
94 | \li binary operators where both arguments are variables: |
---|
95 | AddvvOp, DivvvOp, MulvvOp, PowvvOp, SubvvOp |
---|
96 | |
---|
97 | \param arg |
---|
98 | is a vector of length \c NumArg(op) or 2 (which ever is smaller), |
---|
99 | containing the corresponding argument indices for this operator. |
---|
100 | |
---|
101 | \param npar |
---|
102 | is the number of parameters corresponding to this operation sequence. |
---|
103 | |
---|
104 | \param par |
---|
105 | is a vector of length \a npar containing the parameters |
---|
106 | for this operation sequence; i.e., |
---|
107 | given a parameter index of \c i, the corresponding parameter value is |
---|
108 | \a par[i]. |
---|
109 | |
---|
110 | |
---|
111 | \return |
---|
112 | is a hash code that is between zero and CPPAD_HASH_TABLE_SIZE - 1. |
---|
113 | |
---|
114 | \par Checked Assertions |
---|
115 | \c op must be one of the operators specified above. In addition, |
---|
116 | \li \c std::numeric_limits<unsigned short>::max() >= CPPAD_HASH_TABLE_SIZE |
---|
117 | \li \c sizeof(size_t) is even |
---|
118 | \li \c sizeof(Base) is even |
---|
119 | \li \c sizeof(unsigned short) == 2 |
---|
120 | \li \c size_t(op) < size_t(NumberOp) <= CPPAD_HASH_TABLE_SIZE |
---|
121 | \li if the j-th argument for this operation is a parameter, arg[j] < npar. |
---|
122 | */ |
---|
123 | |
---|
124 | template <class Base> |
---|
125 | unsigned short hash_code( |
---|
126 | OpCode op , |
---|
127 | const addr_t* arg , |
---|
128 | size_t npar , |
---|
129 | const Base* par ) |
---|
130 | { CPPAD_ASSERT_UNKNOWN( |
---|
131 | std::numeric_limits<unsigned short>::max() |
---|
132 | >= |
---|
133 | CPPAD_HASH_TABLE_SIZE |
---|
134 | ); |
---|
135 | CPPAD_ASSERT_UNKNOWN( size_t (op) < size_t(NumberOp) ); |
---|
136 | CPPAD_ASSERT_UNKNOWN( sizeof(unsigned short) == 2 ); |
---|
137 | CPPAD_ASSERT_UNKNOWN( sizeof(addr_t) % 2 == 0 ); |
---|
138 | CPPAD_ASSERT_UNKNOWN( sizeof(Base) % 2 == 0 ); |
---|
139 | unsigned short op_fac = static_cast<unsigned short> ( |
---|
140 | CPPAD_HASH_TABLE_SIZE / static_cast<unsigned short>(NumberOp) |
---|
141 | ); |
---|
142 | CPPAD_ASSERT_UNKNOWN( op_fac > 0 ); |
---|
143 | |
---|
144 | // number of shorts per addr_t value |
---|
145 | size_t short_addr_t = sizeof(addr_t) / 2; |
---|
146 | |
---|
147 | // number of shorts per Base value |
---|
148 | size_t short_base = sizeof(Base) / 2; |
---|
149 | |
---|
150 | // initialize with value that separates operators as much as possible |
---|
151 | unsigned short code = static_cast<unsigned short>( |
---|
152 | static_cast<unsigned short>(op) * op_fac |
---|
153 | ); |
---|
154 | |
---|
155 | // now code in the operands |
---|
156 | size_t i; |
---|
157 | const unsigned short* v; |
---|
158 | |
---|
159 | // first argument |
---|
160 | switch(op) |
---|
161 | { // Binary operators where first arugment is a parameter. |
---|
162 | // Code parameters by value instead of |
---|
163 | // by index for two reasons. One, it gives better separation. |
---|
164 | // Two, different indices can be same parameter value. |
---|
165 | case AddpvOp: |
---|
166 | case DivpvOp: |
---|
167 | case MulpvOp: |
---|
168 | case PowpvOp: |
---|
169 | case SubpvOp: |
---|
170 | CPPAD_ASSERT_UNKNOWN( NumArg(op) == 2 ); |
---|
171 | v = reinterpret_cast<const unsigned short*>(par + arg[0]); |
---|
172 | i = short_base; |
---|
173 | while(i--) |
---|
174 | code += v[i]; |
---|
175 | v = reinterpret_cast<const unsigned short*>(arg + 1); |
---|
176 | i = short_addr_t; |
---|
177 | while(i--) |
---|
178 | code += v[i]; |
---|
179 | break; |
---|
180 | |
---|
181 | // Binary operator where first argument is an index and |
---|
182 | // second is a variable (same as both variables). |
---|
183 | case DisOp: |
---|
184 | |
---|
185 | // Binary operators where both arguments are variables |
---|
186 | case AddvvOp: |
---|
187 | case DivvvOp: |
---|
188 | case MulvvOp: |
---|
189 | case PowvvOp: |
---|
190 | case SubvvOp: |
---|
191 | CPPAD_ASSERT_UNKNOWN( NumArg(op) == 2 ); |
---|
192 | v = reinterpret_cast<const unsigned short*>(arg + 0); |
---|
193 | i = 2 * short_addr_t; |
---|
194 | while(i--) |
---|
195 | code += v[i]; |
---|
196 | break; |
---|
197 | |
---|
198 | // Binary operators where second arugment is a parameter. |
---|
199 | case DivvpOp: |
---|
200 | case PowvpOp: |
---|
201 | case SubvpOp: |
---|
202 | CPPAD_ASSERT_UNKNOWN( NumArg(op) == 2 ); |
---|
203 | v = reinterpret_cast<const unsigned short*>(arg + 0); |
---|
204 | i = short_addr_t; |
---|
205 | while(i--) |
---|
206 | code += v[i]; |
---|
207 | v = reinterpret_cast<const unsigned short*>(par + arg[1]); |
---|
208 | i = short_base; |
---|
209 | while(i--) |
---|
210 | code += v[i]; |
---|
211 | break; |
---|
212 | |
---|
213 | // Unary operators |
---|
214 | case AbsOp: |
---|
215 | case AcosOp: |
---|
216 | case AcoshOp: |
---|
217 | case AsinOp: |
---|
218 | case AsinhOp: |
---|
219 | case AtanOp: |
---|
220 | case CosOp: |
---|
221 | case CoshOp: |
---|
222 | case ErfOp: |
---|
223 | case ExpOp: |
---|
224 | case LogOp: |
---|
225 | case SignOp: |
---|
226 | case SinOp: |
---|
227 | case SinhOp: |
---|
228 | case SqrtOp: |
---|
229 | case TanOp: |
---|
230 | case TanhOp: |
---|
231 | CPPAD_ASSERT_UNKNOWN( NumArg(op) == 1 || op == ErfOp ); |
---|
232 | v = reinterpret_cast<const unsigned short*>(arg + 0); |
---|
233 | i = short_addr_t; |
---|
234 | while(i--) |
---|
235 | code += v[i]; |
---|
236 | break; |
---|
237 | |
---|
238 | // should have been one of he cases above |
---|
239 | default: |
---|
240 | CPPAD_ASSERT_UNKNOWN(false); |
---|
241 | } |
---|
242 | |
---|
243 | return code % CPPAD_HASH_TABLE_SIZE; |
---|
244 | } |
---|
245 | |
---|
246 | } // END_CPPAD_NAMESPACE |
---|
247 | # endif |
---|