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