Epetra Package Browser (Single Doxygen Collection) Development
Loading...
Searching...
No Matches
Epetra_HashTable.h
Go to the documentation of this file.
1/*
2//@HEADER
3// ************************************************************************
4//
5// Epetra: Linear Algebra Services Package
6// Copyright 2011 Sandia Corporation
7//
8// Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
9// the U.S. Government retains certain rights in this software.
10//
11// Redistribution and use in source and binary forms, with or without
12// modification, are permitted provided that the following conditions are
13// met:
14//
15// 1. Redistributions of source code must retain the above copyright
16// notice, this list of conditions and the following disclaimer.
17//
18// 2. Redistributions in binary form must reproduce the above copyright
19// notice, this list of conditions and the following disclaimer in the
20// documentation and/or other materials provided with the distribution.
21//
22// 3. Neither the name of the Corporation nor the names of the
23// contributors may be used to endorse or promote products derived from
24// this software without specific prior written permission.
25//
26// THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
27// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
28// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
29// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
30// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
31// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
32// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
33// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
34// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
35// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
36// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
37//
38// Questions? Contact Michael A. Heroux (maherou@sandia.gov)
39//
40// ************************************************************************
41//@HEADER
42*/
43
44#ifndef Epetra_HashTable_H_
45#define Epetra_HashTable_H_
46
47#include "Epetra_Object.h"
48
49template<typename value_type>
51{
52 struct Node
53 {
54 long long Key;
55 value_type Value;
57
58 Node( const long long key = 0, const value_type value = 0, Node * ptr = 0 )
59 : Key(key), Value(value), Ptr(ptr) {}
60
61 private:
62 Node(const Node& src)
63 : Key(src.Key), Value(src.Value), Ptr(src.Ptr) {}
64
65 Node& operator=(const Node& src)
66 { Key = src.Key; Value = src.Value; Ptr = src.Ptr; return(*this); }
67 };
68
70 long long Size_;
71 unsigned int Seed_;
72
73 int Func( const long long key ) {
74 int intkey = (int) ((key & 0x000000007fffffffLL) + ((key & 0x7fffffff80000000LL) >> 31));
75 return (int) ((Seed_ ^ intkey)%Size_);
76 }
77
78 public:
79
80 Epetra_HashTable( const int size, const unsigned int seed = (2654435761U) )
81 : Container_(NULL),
82 Size_(size),
83 Seed_(seed)
84 {
85 if (size<=0)
86 throw ReportError( "Bad Hash Table Size: " + toString(size), -1 );
87
88 Container_ = new Node * [size];
89 for( int i = 0; i < size; ++i ) Container_[i] = 0;
90 }
91
93 : Container_(NULL),
94 Size_(obj.Size_),
95 Seed_(obj.Seed_)
96 {
97 Container_ = new Node * [Size_];
98 for( int i = 0; i < Size_; ++i ) Container_[i] = 0;
99 for( int i = 0; i < Size_; ++i )
100 {
101 Node * ptr = obj.Container_[i];
102 while( ptr ) { Add( ptr->Key, ptr->Value ); ptr = ptr->Ptr; }
103 }
104 }
105
107 {
108 Node * ptr1;
109 Node * ptr2;
110 for( int i = 0; i < Size_; ++i )
111 {
112 ptr1 = Container_[i];
113 while( ptr1 ) { ptr2 = ptr1; ptr1 = ptr1->Ptr; delete ptr2; }
114 }
115
116 delete [] Container_;
117 }
118
119 void Add( const long long key, const value_type value )
120 {
121 int v = Func(key);
122 Node * n1 = Container_[v];
123 Container_[v] = new Node(key,value,n1);
124 }
125
126 value_type Get( const long long key )
127 {
128 Node * n = Container_[ Func(key) ];
129 while( n && (n->Key != key) ) n = n->Ptr;
130 if( n ) return n->Value;
131 else return -1;
132 }
133
134 private:
136 {
137 (void)src;
138 //not currently supported
139 bool throw_error = true;
140 if (throw_error) {
141 throw ReportError("Epetra_HashTable::operator= not supported.",-1);
142 }
143 return(*this);
144 }
145
146};
147
148#endif
unsigned int Seed_
void Add(const long long key, const value_type value)
Epetra_HashTable(const int size, const unsigned int seed=(2654435761U))
Epetra_HashTable & operator=(const Epetra_HashTable &src)
Epetra_HashTable(const Epetra_HashTable &obj)
int Func(const long long key)
value_type Get(const long long key)
Epetra_Object: The base Epetra class.
Definition: Epetra_Object.h:57
virtual int ReportError(const std::string Message, int ErrorCode) const
Error reporting method.
std::string toString(const int &x) const
Node & operator=(const Node &src)
Node(const Node &src)
Node(const long long key=0, const value_type value=0, Node *ptr=0)