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