Epetra Package Browser (Single Doxygen Collection) Development
Epetra_HashTable.h
Go to the documentation of this file.
00001 /*
00002 //@HEADER
00003 // ************************************************************************
00004 // 
00005 //               Epetra: Linear Algebra Services Package 
00006 //                 Copyright 2011 Sandia Corporation
00007 // 
00008 // Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
00009 // the U.S. Government retains certain rights in this software.
00010 //
00011 // Redistribution and use in source and binary forms, with or without
00012 // modification, are permitted provided that the following conditions are
00013 // met:
00014 //
00015 // 1. Redistributions of source code must retain the above copyright
00016 // notice, this list of conditions and the following disclaimer.
00017 //
00018 // 2. Redistributions in binary form must reproduce the above copyright
00019 // notice, this list of conditions and the following disclaimer in the
00020 // documentation and/or other materials provided with the distribution.
00021 //
00022 // 3. Neither the name of the Corporation nor the names of the
00023 // contributors may be used to endorse or promote products derived from
00024 // this software without specific prior written permission.
00025 //
00026 // THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
00027 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00028 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
00029 // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
00030 // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
00031 // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
00032 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
00033 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
00034 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
00035 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00036 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00037 //
00038 // Questions? Contact Michael A. Heroux (maherou@sandia.gov) 
00039 // 
00040 // ************************************************************************
00041 //@HEADER
00042 */
00043 
00044 #ifndef Epetra_HashTable_H_
00045 #define Epetra_HashTable_H_
00046 
00047 #include "Epetra_Object.h"
00048 
00049 template<typename value_type>
00050 class Epetra_HashTable : public Epetra_Object
00051 {
00052   struct Node
00053   {
00054      long long Key;
00055      value_type Value;
00056      Node * Ptr;
00057 
00058      Node( const long long key = 0, const value_type value = 0, Node * ptr = 0 )
00059      : Key(key), Value(value), Ptr(ptr) {}
00060 
00061     private:
00062      Node(const Node& src)
00063        : Key(src.Key), Value(src.Value), Ptr(src.Ptr) {}
00064 
00065     Node& operator=(const Node& src)
00066     { Key = src.Key; Value = src.Value; Ptr = src.Ptr; return(*this); }
00067   };
00068 
00069   Node ** Container_;
00070   long long Size_;
00071   unsigned int Seed_;
00072 
00073   int Func( const long long key ) { 
00074     int intkey = (int) ((key & 0x000000007fffffffLL) + ((key & 0x7fffffff80000000LL) >> 31));
00075     return (int) ((Seed_ ^ intkey)%Size_);
00076   } 
00077      
00078  public:
00079 
00080   Epetra_HashTable( const int size, const unsigned int seed = (2654435761U) )
00081   : Container_(NULL),
00082     Size_(size),
00083     Seed_(seed)
00084   {
00085     if (size<=0)
00086       throw ReportError( "Bad Hash Table Size: " + toString(size), -1 );
00087 
00088     Container_ = new Node * [size];
00089     for( int i = 0; i < size; ++i ) Container_[i] = 0;
00090   }
00091 
00092   Epetra_HashTable( const Epetra_HashTable & obj )
00093   : Container_(NULL),
00094     Size_(obj.Size_),
00095     Seed_(obj.Seed_)
00096   {
00097     Container_ = new Node * [Size_];
00098     for( int i = 0; i < Size_; ++i ) Container_[i] = 0;
00099     for( int i = 0; i < Size_; ++i )
00100     {
00101       Node * ptr = obj.Container_[i];
00102       while( ptr ) { Add( ptr->Key, ptr->Value ); ptr = ptr->Ptr; }
00103     }
00104   }
00105 
00106   ~Epetra_HashTable()
00107   {
00108     Node * ptr1;
00109     Node * ptr2;
00110     for( int i = 0; i < Size_; ++i )
00111     {
00112       ptr1 = Container_[i];
00113       while( ptr1 ) { ptr2 = ptr1; ptr1 = ptr1->Ptr; delete ptr2; }
00114     }
00115 
00116     delete [] Container_;
00117   }
00118 
00119   void Add( const long long key, const value_type value )
00120   {
00121     int v = Func(key);
00122     Node * n1 = Container_[v];
00123     Container_[v] = new Node(key,value,n1);
00124   }
00125 
00126   value_type Get( const long long key )
00127   {
00128     Node * n = Container_[ Func(key) ];
00129     while( n && (n->Key != key) ) n = n->Ptr;
00130     if( n ) return n->Value;
00131     else    return -1;
00132   }
00133 
00134  private:
00135   Epetra_HashTable& operator=(const Epetra_HashTable& src)
00136     {
00137       (void)src;
00138       //not currently supported
00139       bool throw_error = true;
00140       if (throw_error) {
00141   throw ReportError("Epetra_HashTable::operator= not supported.",-1);
00142       }
00143       return(*this);
00144     }
00145 
00146 };
00147 
00148 #endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines