CppAD: A C++ Algorithmic Differentiation Package  20130918
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-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
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines