CppAD: A C++ Algorithmic Differentiation Package 20110419
|
00001 /* $Id$ */ 00002 # ifndef CPPAD_HASH_CODE_INCLUDED 00003 # define CPPAD_HASH_CODE_INCLUDED 00004 00005 /* -------------------------------------------------------------------------- 00006 CppAD: C++ Algorithmic Differentiation: Copyright (C) 2003-10 Bradley M. Bell 00007 00008 CppAD is distributed under multiple licenses. This distribution is under 00009 the terms of the 00010 Common 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 \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 65536 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 - 1 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-1) 00056 ); 00057 CPPAD_ASSERT_UNKNOWN( sizeof(unsigned short) == 2 ); 00058 CPPAD_ASSERT_UNKNOWN( sizeof(value) % 2 == 0 ); 00059 static unsigned short n = sizeof(value) / 2; 00060 00061 const unsigned short* v; 00062 size_t i; 00063 unsigned short code; 00064 00065 v = reinterpret_cast<const unsigned short*>(& value); 00066 i = n - 1; 00067 code = v[i]; 00068 while(i--) 00069 code += v[i]; 00070 00071 return code; 00072 } 00073 00074 /*! 00075 Specialized hash code for a CppAD operator and its arguments. 00076 00077 \param op 00078 is the operator that we are computing a hash code for. 00079 If it is not one of the following operartors, the operator is not 00080 hash coded and zero is returned: 00081 00082 \li unary operators: 00083 AbsOp, AcosOp, AsinOp, AtanOp, CosOp, CoshOp, DisOp, 00084 ExpOp, LogOp, SinOp, SinhOp, SqrtOp 00085 00086 \li binary operators where first argument is a parameter: 00087 AddpvOp, DivpvOp, MulpvOp, PowpvOp, SubpvOp, 00088 00089 \li binary operators where second argument is a parameter: 00090 DivvpOp, PowvpOp, SubvpOp 00091 00092 \li binary operators where both arguments are parameters: 00093 AddvvOp, DivvvOp, MulvvOp, PowvvOp, SubvvOp 00094 00095 \param arg 00096 is a vector of length \c NumArg(op) or 2 (which ever is smaller), 00097 containing the corresponding argument indices for this operator. 00098 00099 \param npar 00100 is the number of parameters corresponding to this operation sequence. 00101 00102 \param par 00103 is a vector of length \a npar containing the parameters 00104 for this operation sequence; i.e., 00105 given a parameter index of \c i, the corresponding parameter value is 00106 \a par[i]. 00107 00108 00109 \return 00110 is a hash code that is between zero and CPPAD_HASH_TABLE_SIZE - 1. 00111 00112 \par Checked Assertions 00113 \c op must be one of the operators specified above. In addition, 00114 \li \c std::numeric_limits<unsigned short>::max() == CPPAD_HASH_TABLE_SIZE - 1 00115 \li \c sizeof(size_t) is even 00116 \li \c sizeof(Base) is even 00117 \li \c sizeof(unsigned short) == 2 00118 \li \c size_t(op) <= size_t(SubvvOp) < CPPAD_HASH_TABLE_SIZE 00119 \li if the j-th argument for this operation is a parameter, arg[j] < npar. 00120 */ 00121 00122 template <class Base> 00123 unsigned short hash_code( 00124 OpCode op , 00125 const size_t* arg , 00126 size_t npar , 00127 const Base* par ) 00128 { CPPAD_ASSERT_UNKNOWN( 00129 std::numeric_limits<unsigned short>::max() 00130 == 00131 (CPPAD_HASH_TABLE_SIZE-1) 00132 ); 00133 CPPAD_ASSERT_UNKNOWN( size_t (op) <= size_t(SubvvOp) ); 00134 CPPAD_ASSERT_UNKNOWN( sizeof(unsigned short) == 2 ); 00135 CPPAD_ASSERT_UNKNOWN( sizeof(size_t) % 2 == 0 ); 00136 CPPAD_ASSERT_UNKNOWN( sizeof(Base) % 2 == 0 ); 00137 static unsigned short op_fac = static_cast<unsigned short> ( 00138 CPPAD_HASH_TABLE_SIZE / ( 1 + static_cast<unsigned short>(SubvvOp) ) 00139 ); 00140 CPPAD_ASSERT_UNKNOWN( op_fac > 0 ); 00141 00142 // number of shorts per size_t value 00143 size_t short_size_t = sizeof(size_t) / 2; 00144 00145 // number of shorts per Base value 00146 size_t short_base = sizeof(Base) / 2; 00147 00148 // initialize with value that separates operators as much as possible 00149 unsigned short code = static_cast<unsigned short>( 00150 static_cast<unsigned short>(op) * op_fac 00151 ); 00152 00153 // now code in the operands 00154 size_t i; 00155 const unsigned short* v; 00156 00157 // first argument 00158 switch(op) 00159 { // Binary operators where first arugment is a parameter. 00160 // Code parameters by value instead of 00161 // by index for two reasons. One, it gives better separation. 00162 // Two, different indices can be same parameter value. 00163 case AddpvOp: 00164 case DivpvOp: 00165 case MulpvOp: 00166 case PowpvOp: 00167 case SubpvOp: 00168 CPPAD_ASSERT_UNKNOWN( NumArg(op) == 2 ); 00169 v = reinterpret_cast<const unsigned short*>(par + arg[0]); 00170 i = short_base; 00171 while(i--) 00172 code += v[i]; 00173 v = reinterpret_cast<const unsigned short*>(arg + 1); 00174 i = short_size_t; 00175 while(i--) 00176 code += v[i]; 00177 break; 00178 00179 // Binary operators where both arguments are variables 00180 case AddvvOp: 00181 case DivvvOp: 00182 case MulvvOp: 00183 case PowvvOp: 00184 case SubvvOp: 00185 CPPAD_ASSERT_UNKNOWN( NumArg(op) == 2 ); 00186 v = reinterpret_cast<const unsigned short*>(arg + 0); 00187 i = 2 * short_size_t; 00188 while(i--) 00189 code += v[i]; 00190 break; 00191 00192 // Binary operators where second arugment is a parameter. 00193 case DivvpOp: 00194 case PowvpOp: 00195 case SubvpOp: 00196 CPPAD_ASSERT_UNKNOWN( NumArg(op) == 2 ); 00197 v = reinterpret_cast<const unsigned short*>(arg + 0); 00198 i = short_size_t; 00199 while(i--) 00200 code += v[i]; 00201 v = reinterpret_cast<const unsigned short*>(par + arg[1]); 00202 i = short_base; 00203 while(i--) 00204 code += v[i]; 00205 break; 00206 00207 // Unary operators 00208 case AbsOp: 00209 case AcosOp: 00210 case AsinOp: 00211 case AtanOp: 00212 case CosOp: 00213 case CoshOp: 00214 case DisOp: 00215 case ExpOp: 00216 case LogOp: 00217 case SinOp: 00218 case SinhOp: 00219 case SqrtOp: 00220 v = reinterpret_cast<const unsigned short*>(arg + 0); 00221 i = short_size_t; 00222 while(i--) 00223 code += v[i]; 00224 break; 00225 00226 // return zero if not one of the cases above 00227 default: 00228 CPPAD_ASSERT_UNKNOWN(false); 00229 } 00230 00231 return code; 00232 } 00233 00234 CPPAD_END_NAMESPACE 00235 # endif