CppAD: A C++ Algorithmic Differentiation Package
20130918
|
00001 /* $Id$ */ 00002 # ifndef CPPAD_HASH_CODE_INCLUDED 00003 # define CPPAD_HASH_CODE_INCLUDED 00004 00005 /* -------------------------------------------------------------------------- 00006 CppAD: C++ Algorithmic Differentiation: Copyright (C) 2003-14 Bradley M. Bell 00007 00008 CppAD is distributed under multiple licenses. This distribution is under 00009 the terms of the 00010 Eclipse Public License Version 1.0. 00011 00012 A copy of this license is included in the COPYING file of this distribution. 00013 Please visit http://www.coin-or.org/CppAD/ for information on other licenses. 00014 -------------------------------------------------------------------------- */ 00015 00016 namespace CppAD { // BEGIN_CPPAD_NAMESPACE 00017 /*! 00018 \file hash_code.hpp 00019 CppAD hashing utility. 00020 */ 00021 00022 /*! 00023 \def CPPAD_HASH_TABLE_SIZE 00024 the codes retruned by hash_code are between zero and CPPAD_HASH_TABLE_SIZE 00025 minus one. 00026 */ 00027 # define CPPAD_HASH_TABLE_SIZE 10000 00028 00029 /*! 00030 General purpose hash code for an arbitrary value. 00031 00032 \tparam Value 00033 is the type of the argument being hash coded. 00034 It should be a plain old data class; i.e., 00035 the values included in the equality operator in the object and 00036 not pointed to by the object. 00037 00038 \param value 00039 the value that we are generating a hash code for. 00040 00041 \return 00042 is a hash code that is between zero and CPPAD_HASH_TABLE_SIZE - 1. 00043 00044 \par Checked Assertions 00045 \li \c std::numeric_limits<unsigned short>::max() >= CPPAD_HASH_TABLE_SIZE 00046 \li \c sizeof(value) is even 00047 \li \c sizeof(unsigned short) == 2 00048 */ 00049 00050 template <class Value> 00051 unsigned short hash_code(const Value& value) 00052 { CPPAD_ASSERT_UNKNOWN( 00053 std::numeric_limits<unsigned short>::max() 00054 >= 00055 CPPAD_HASH_TABLE_SIZE 00056 ); 00057 CPPAD_ASSERT_UNKNOWN( sizeof(unsigned short) == 2 ); 00058 CPPAD_ASSERT_UNKNOWN( sizeof(value) % 2 == 0 ); 00059 # 00060 const unsigned short* v 00061 = reinterpret_cast<const unsigned short*>(& value); 00062 # 00063 size_t i = sizeof(value) / 2 - 1; 00064 # 00065 unsigned short code = v[i]; 00066 # 00067 while(i--) 00068 code += v[i]; 00069 00070 return code % CPPAD_HASH_TABLE_SIZE; 00071 } 00072 00073 /*! 00074 Specialized hash code for a CppAD operator and its arguments. 00075 00076 \param op 00077 is the operator that we are computing a hash code for. 00078 If it is not one of the following operartors, the operator is not 00079 hash coded and zero is returned: 00080 00081 \li unary operators: 00082 AbsOp, AcosOp, AsinOp, AtanOp, CosOp, CoshOp, DisOp, 00083 ExpOp, LogOp, SinOp, SinhOp, SqrtOp, TanOp, TanhOp 00084 00085 \li binary operators where first argument is a parameter: 00086 AddpvOp, DivpvOp, MulpvOp, PowpvOp, SubpvOp, 00087 00088 \li binary operators where second argument is a parameter: 00089 DivvpOp, PowvpOp, SubvpOp 00090 00091 \li binary operators where both arguments are parameters: 00092 AddvvOp, DivvvOp, MulvvOp, PowvvOp, SubvvOp 00093 00094 \param arg 00095 is a vector of length \c NumArg(op) or 2 (which ever is smaller), 00096 containing the corresponding argument indices for this operator. 00097 00098 \param npar 00099 is the number of parameters corresponding to this operation sequence. 00100 00101 \param par 00102 is a vector of length \a npar containing the parameters 00103 for this operation sequence; i.e., 00104 given a parameter index of \c i, the corresponding parameter value is 00105 \a par[i]. 00106 00107 00108 \return 00109 is a hash code that is between zero and CPPAD_HASH_TABLE_SIZE - 1. 00110 00111 \par Checked Assertions 00112 \c op must be one of the operators specified above. In addition, 00113 \li \c std::numeric_limits<unsigned short>::max() >= CPPAD_HASH_TABLE_SIZE 00114 \li \c sizeof(size_t) is even 00115 \li \c sizeof(Base) is even 00116 \li \c sizeof(unsigned short) == 2 00117 \li \c size_t(op) < size_t(NumberOp) <= CPPAD_HASH_TABLE_SIZE 00118 \li if the j-th argument for this operation is a parameter, arg[j] < npar. 00119 */ 00120 00121 template <class Base> 00122 unsigned short hash_code( 00123 OpCode op , 00124 const addr_t* arg , 00125 size_t npar , 00126 const Base* par ) 00127 { CPPAD_ASSERT_UNKNOWN( 00128 std::numeric_limits<unsigned short>::max() 00129 >= 00130 CPPAD_HASH_TABLE_SIZE 00131 ); 00132 CPPAD_ASSERT_UNKNOWN( size_t (op) < size_t(NumberOp) ); 00133 CPPAD_ASSERT_UNKNOWN( sizeof(unsigned short) == 2 ); 00134 CPPAD_ASSERT_UNKNOWN( sizeof(addr_t) % 2 == 0 ); 00135 CPPAD_ASSERT_UNKNOWN( sizeof(Base) % 2 == 0 ); 00136 unsigned short op_fac = static_cast<unsigned short> ( 00137 CPPAD_HASH_TABLE_SIZE / static_cast<unsigned short>(NumberOp) 00138 ); 00139 CPPAD_ASSERT_UNKNOWN( op_fac > 0 ); 00140 00141 // number of shorts per addr_t value 00142 size_t short_addr_t = sizeof(addr_t) / 2; 00143 00144 // number of shorts per Base value 00145 size_t short_base = sizeof(Base) / 2; 00146 00147 // initialize with value that separates operators as much as possible 00148 unsigned short code = static_cast<unsigned short>( 00149 static_cast<unsigned short>(op) * op_fac 00150 ); 00151 00152 // now code in the operands 00153 size_t i; 00154 const unsigned short* v; 00155 00156 // first argument 00157 switch(op) 00158 { // Binary operators where first arugment is a parameter. 00159 // Code parameters by value instead of 00160 // by index for two reasons. One, it gives better separation. 00161 // Two, different indices can be same parameter value. 00162 case AddpvOp: 00163 case DivpvOp: 00164 case MulpvOp: 00165 case PowpvOp: 00166 case SubpvOp: 00167 CPPAD_ASSERT_UNKNOWN( NumArg(op) == 2 ); 00168 v = reinterpret_cast<const unsigned short*>(par + arg[0]); 00169 i = short_base; 00170 while(i--) 00171 code += v[i]; 00172 v = reinterpret_cast<const unsigned short*>(arg + 1); 00173 i = short_addr_t; 00174 while(i--) 00175 code += v[i]; 00176 break; 00177 00178 // Binary operators where both arguments are variables 00179 case AddvvOp: 00180 case DivvvOp: 00181 case MulvvOp: 00182 case PowvvOp: 00183 case SubvvOp: 00184 CPPAD_ASSERT_UNKNOWN( NumArg(op) == 2 ); 00185 v = reinterpret_cast<const unsigned short*>(arg + 0); 00186 i = 2 * short_addr_t; 00187 while(i--) 00188 code += v[i]; 00189 break; 00190 00191 // Binary operators where second arugment is a parameter. 00192 case DivvpOp: 00193 case PowvpOp: 00194 case SubvpOp: 00195 CPPAD_ASSERT_UNKNOWN( NumArg(op) == 2 ); 00196 v = reinterpret_cast<const unsigned short*>(arg + 0); 00197 i = short_addr_t; 00198 while(i--) 00199 code += v[i]; 00200 v = reinterpret_cast<const unsigned short*>(par + arg[1]); 00201 i = short_base; 00202 while(i--) 00203 code += v[i]; 00204 break; 00205 00206 // Unary operators 00207 case AbsOp: 00208 case AcosOp: 00209 case AsinOp: 00210 case AtanOp: 00211 case CosOp: 00212 case CoshOp: 00213 case DisOp: 00214 case ExpOp: 00215 case LogOp: 00216 case SignOp: 00217 case SinOp: 00218 case SinhOp: 00219 case SqrtOp: 00220 case TanOp: 00221 case TanhOp: 00222 v = reinterpret_cast<const unsigned short*>(arg + 0); 00223 i = short_addr_t; 00224 while(i--) 00225 code += v[i]; 00226 break; 00227 00228 // should have been one of he cases above 00229 default: 00230 CPPAD_ASSERT_UNKNOWN(false); 00231 } 00232 00233 return code % CPPAD_HASH_TABLE_SIZE; 00234 } 00235 00236 } // END_CPPAD_NAMESPACE 00237 # endif