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(n_keys);
00055 //
00056 //    n_keys - maximum number of keys (This will be the n_keys with zero 
00057 //             collisons.)
00058 //
00059 // 3) use it, then delete it:
00060 //
00061 //    Hash.get(key, value)       --> returns the value stored on key, or 0.0 
00062 //                                   if not found.
00063 //    Hash.set(key, value)       --> sets the value in the hash table, replace
00064 //                                   existing values.
00065 //    Hash.set(key, value, true) --> to sum into an already inserted value
00066 //    Hash.arrayify(...)
00067 //
00068 // 4) clean memory:
00069 //
00070 //    Hash.reset();
00071 //
00072 // \author Marzio Sala, ETHZ/COLAB
00073 //
00074 // \date 30-Jun-06
00075 // ============================================================================ 
00076 
00077 class Ifpack_HashTable 
00078 {
00079   public:
00081     Ifpack_HashTable(const int n_keys = 1031, const int n_sets = 1)
00082     {
00083       n_keys_ = getRecommendedHashSize(n_keys) ;
00084       n_sets_ = n_sets;
00085       seed_ = (2654435761U);
00086 
00087       keys_.reserve(50);
00088       vals_.reserve(50);
00089 
00090       keys_.resize(n_sets_);
00091       vals_.resize(n_sets_);
00092 
00093       for (int i = 0; i < n_sets_; ++i)
00094       {
00095         keys_[i].resize(n_keys_);
00096         vals_[i].resize(n_keys_);
00097       }
00098 
00099       counter_.resize(n_keys_);
00100       for (int i = 0; i < n_keys_; ++i) counter_[i] = 0;
00101     }
00102 
00104     inline double get(const int key)
00105     {
00106       int hashed_key = doHash(key);
00107 
00108       for (int set_ptr = 0; set_ptr < counter_[hashed_key]; ++set_ptr)
00109       {
00110         if (keys_[set_ptr][hashed_key] == key)  
00111           return(vals_[set_ptr][hashed_key]);
00112       }
00113 
00114       return(0.0);
00115     }
00116 
00118     inline void set(const int key, const double value,
00119                     const bool addToValue = false)
00120     {
00121       int hashed_key = doHash(key);
00122       int& hashed_counter = counter_[hashed_key];
00123 
00124       for (int set_ptr = 0; set_ptr < hashed_counter; ++set_ptr)
00125       {
00126         if (keys_[set_ptr][hashed_key] == key)
00127         {
00128           if (addToValue)
00129             vals_[set_ptr][hashed_key] += value;
00130           else
00131             vals_[set_ptr][hashed_key] = value;
00132           return;
00133         }
00134       }
00135 
00136       if (hashed_counter < n_sets_)
00137       {
00138         keys_[hashed_counter][hashed_key] = key;
00139         vals_[hashed_counter][hashed_key] = value;
00140         ++hashed_counter;
00141         return;
00142       }
00143 
00144       std::vector<int> new_key;
00145       std::vector<double> new_val;
00146 
00147       keys_.push_back(new_key);
00148       vals_.push_back(new_val);
00149       keys_[n_sets_].resize(n_keys_);
00150       vals_[n_sets_].resize(n_keys_);
00151 
00152       keys_[n_sets_][hashed_key] = key;
00153       vals_[n_sets_][hashed_key] = value;
00154       ++hashed_counter;
00155       ++n_sets_;
00156     }
00157 
00162     inline void reset()
00163     {
00164       memset(&counter_[0], 0, sizeof(int) * n_keys_);
00165     }
00166 
00168     inline int getNumEntries() const 
00169     {
00170       int n_entries = 0;
00171       for (int key = 0; key < n_keys_; ++key)
00172         n_entries += counter_[key];
00173       return(n_entries);
00174     }
00175 
00177     void arrayify(int* key_array, double* val_array)
00178     {
00179       int count = 0;
00180       for (int key = 0; key < n_keys_; ++key)
00181         for (int set_ptr = 0; set_ptr < counter_[key]; ++set_ptr)
00182         {
00183           key_array[count] = keys_[set_ptr][key];
00184           val_array[count] = vals_[set_ptr][key];
00185           ++count;
00186         }
00187     }
00188 
00190     void print()
00191     {
00192       cout << "n_keys = " << n_keys_ << endl;
00193       cout << "n_sets = " << n_sets_ << endl;
00194     }
00195 
00196     int getRecommendedHashSize (int n)
00197     {
00198         /* Prime number approximately in the middle of the range [2^x..2^(x+1)]
00199          * is in primes[x-1]. Every prime number stored is approximately two 
00200          * times the previous one, so hash table size doubles every time.
00201          */
00202         int primes[] = {
00203         3, 7, 13, 23, 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
00204         49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469,
00205         12582917, 25165842, 50331653, 100663319, 201326611, 402653189,
00206         805306457, 1610612741 } ;
00207         int i, hsize ;
00208 
00209         /* SRSR : err on the side of performance and choose the next largest 
00210          * prime number. One can also choose primes[i-1] below to cut the 
00211          * memory by half.
00212          */
00213         hsize = primes[29] ;
00214         for (i = 6 ; i < 30 ; i++)
00215         {
00216             if (n <= primes[i])
00217             {
00218                 /*hsize = (i == 0 ? n : primes[i-1]) ;*/
00219                 hsize = primes[i] ;
00220                 break ;
00221             }
00222         }
00223 
00224         return hsize ;
00225     }
00226 
00227   private:
00229     inline int doHash(const int key)
00230     {
00231       return (key % n_keys_);
00232       //return ((seed_ ^ key) % n_keys_);
00233     }
00234 
00235     int n_keys_;
00236     int n_sets_;
00237     std::vector<std::vector<double> > vals_;
00238     std::vector<std::vector<int> > keys_;
00239     std::vector<int> counter_;
00240     unsigned int seed_;
00241 };
00242 #endif
 All Classes Files Functions Variables Enumerations Friends
Generated on Wed Apr 13 10:05:23 2011 for IFPACK by  doxygen 1.6.3