CppAD: A C++ Algorithmic Differentiation Package 20110419
hash_code.hpp
Go to the documentation of this file.
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