Ifpack_HashTable.h

00001 //@HEADER
00002 /*
00003 ************************************************************************
00004 
00005               IFPACK: Robust Algebraic Preconditioning Package
00006                 Copyright (2001) Sandia Corporation
00007 
00008 Under terms of Contract DE-AC04-94AL85000, there is a non-exclusive
00009 license for use of this work by or on behalf of the U.S. Government.
00010 
00011 This library is free software; you can redistribute it and/or modify
00012 it under the terms of the GNU Lesser General Public License as
00013 published by the Free Software Foundation; either version 2.1 of the
00014 License, or (at your option) any later version.
00015  
00016 This library is distributed in the hope that it will be useful, but
00017 WITHOUT ANY WARRANTY; without even the implied warranty of
00018 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00019 Lesser General Public License for more details.
00020  
00021 You should have received a copy of the GNU Lesser General Public
00022 License along with this library; if not, write to the Free Software
00023 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
00024 USA
00025 Questions? Contact Michael A. Heroux (maherou@sandia.gov) 
00026 
00027 ************************************************************************
00028 */
00029 //@HEADER
00030 
00031 /* \file Ifpack_HashTable.h
00032  *
00033  * \brief HashTable used in Ifpack_ICT and Ifpack_ILUT.
00034  *
00035  * \author Marzio Sala, ETHZ/D-INFK.
00036  *
00037  * \date Last modified on 30-Jun-06.
00038  */
00039 
00040 #ifndef IFPACK_HASHTABLE_H
00041 #define IFPACK_HASHTABLE_H
00042 
00043 #include "Ifpack_ConfigDefs.h"
00044 
00045 // ============================================================================
00046 // Hash table with good performances and high level of memory reuse.
00047 // Given a maximum number of keys n_keys, this class allocates chunks of memory
00048 // to store n_keys keys and values. 
00049 //
00050 // Usage:
00051 //
00052 // 1) Instantiate a object,
00053 //
00054 //    Ifpack_HashTable Hash(size);
00055 //
00056 //    size should be a prime number, like 2^k - 1.
00057 //
00058 // 3) use it, then delete it:
00059 //
00060 //    Hash.get(key, value)       --> returns the value stored on key, or 0.0 
00061 //                                   if not found.
00062 //    Hash.set(key, value)       --> sets the value in the hash table, replace
00063 //                                   existing values.
00064 //    Hash.set(key, value, true) --> to sum into an already inserted value
00065 //    Hash.arrayify(...)
00066 //
00067 // 4) clean memory:
00068 //
00069 //    Hash.reset();
00070 //
00071 // \author Marzio Sala, ETHZ/COLAB
00072 //
00073 // \date 30-Jun-06
00074 // ============================================================================ 
00075 
00076 class Ifpack_HashTable 
00077 {
00078   public:
00080     Ifpack_HashTable(const int n_keys = 1031, const int n_sets = 1)
00081     {
00082       n_keys_ = n_keys;
00083       n_sets_ = n_sets;
00084       seed_ = (2654435761U);
00085 
00086       keys_.reserve(50);
00087       vals_.reserve(50);
00088 
00089       keys_.resize(n_sets_);
00090       vals_.resize(n_sets_);
00091 
00092       for (int i = 0; i < n_sets_; ++i)
00093       {
00094         keys_[i].resize(n_keys_);
00095         vals_[i].resize(n_keys_);
00096       }
00097 
00098       counter_.resize(n_keys_);
00099       for (int i = 0; i < n_keys_; ++i) counter_[i] = 0;
00100     }
00101 
00103     inline double get(const int key)
00104     {
00105       int hashed_key = doHash(key);
00106 
00107       for (int set = 0; set < counter_[hashed_key]; ++set)
00108       {
00109         if (keys_[set][hashed_key] == key)  
00110           return(vals_[set][hashed_key]);
00111       }
00112 
00113       return(0.0);
00114     }
00115 
00117     inline void set(const int key, const double value,
00118                     const bool addToValue = false)
00119     {
00120       int hashed_key = doHash(key);
00121       int& hashed_counter = counter_[hashed_key];
00122 
00123       for (int set = 0; set < hashed_counter; ++set)
00124       {
00125         if (keys_[set][hashed_key] == key)
00126         {
00127           if (addToValue)
00128             vals_[set][hashed_key] += value;
00129           else
00130             vals_[set][hashed_key] = value;
00131           return;
00132         }
00133       }
00134 
00135       if (hashed_counter < n_sets_)
00136       {
00137         keys_[hashed_counter][hashed_key] = key;
00138         vals_[hashed_counter][hashed_key] = value;
00139         ++hashed_counter;
00140         return;
00141       }
00142 
00143       std::vector<int> new_key;
00144       std::vector<double> new_val;
00145 
00146       keys_.push_back(new_key);
00147       vals_.push_back(new_val);
00148       keys_[n_sets_].resize(n_keys_);
00149       vals_[n_sets_].resize(n_keys_);
00150 
00151       keys_[n_sets_][hashed_key] = key;
00152       vals_[n_sets_][hashed_key] = value;
00153       ++hashed_counter;
00154       ++n_sets_;
00155     }
00156 
00161     inline void reset()
00162     {
00163       memset(&counter_[0], 0, sizeof(int) * n_keys_);
00164     }
00165 
00167     inline int getNumEntries() const 
00168     {
00169       int n_entries = 0;
00170       for (int key = 0; key < n_keys_; ++key)
00171         n_entries += counter_[key];
00172       return(n_entries);
00173     }
00174 
00176     void arrayify(int* key_array, double* val_array)
00177     {
00178       int count = 0;
00179       for (int key = 0; key < n_keys_; ++key)
00180         for (int set = 0; set < counter_[key]; ++set)
00181         {
00182           key_array[count] = keys_[set][key];
00183           val_array[count] = vals_[set][key];
00184           ++count;
00185         }
00186     }
00187 
00189     void print()
00190     {
00191       cout << "n_keys = " << n_keys_ << endl;
00192       cout << "n_sets = " << n_sets_ << endl;
00193     }
00194 
00195   private:
00197     inline int doHash(const int key)
00198     {
00199       return (key % n_keys_);
00200       //return ((seed_ ^ key) % n_keys_);
00201     }
00202 
00203     int n_keys_;
00204     int n_sets_;
00205     std::vector<std::vector<double> > vals_;
00206     std::vector<std::vector<int> > keys_;
00207     std::vector<int> counter_;
00208     unsigned int seed_;
00209 };
00210 #endif

Generated on Tue Oct 20 12:48:53 2009 for IFPACK by doxygen 1.4.7