Ifpack Package Browser (Single Doxygen Collection) Development
Hash_i_dh.c
Go to the documentation of this file.
00001 /*@HEADER
00002 // ***********************************************************************
00003 //
00004 //       Ifpack: Object-Oriented Algebraic Preconditioner Package
00005 //                 Copyright (2009) Sandia Corporation
00006 //
00007 // Under terms of Contract DE-AC04-94AL85000, there is a non-exclusive
00008 // license for use of this work by or on behalf of the U.S. Government.
00009 //
00010 // This library is free software; you can redistribute it and/or modify
00011 // it under the terms of the GNU Lesser General Public License as
00012 // published by the Free Software Foundation; either version 2.1 of the
00013 // License, or (at your option) any later version.
00014 //
00015 // This library is distributed in the hope that it will be useful, but
00016 // WITHOUT ANY WARRANTY; without even the implied warranty of
00017 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00018 // Lesser General Public License for more details.
00019 //
00020 // You should have received a copy of the GNU Lesser General Public
00021 // License along with this library; if not, write to the Free Software
00022 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
00023 // USA
00024 // Questions? Contact Michael A. Heroux (maherou@sandia.gov)
00025 //
00026 // ***********************************************************************
00027 //@HEADER
00028 */
00029 
00030 #include "Hash_i_dh.h"
00031 #include "Parser_dh.h"
00032 #include "Mem_dh.h"
00033 
00034 #define DEFAULT_TABLE_SIZE 16
00035 
00036 static void rehash_private (Hash_i_dh h);
00037 
00038 
00039 /*--------------------------------------------------------------
00040  * hash functions (double hashing is used)
00041  *--------------------------------------------------------------*/
00042 #define HASH_1(k,size,idxOut)    \
00043          {  *idxOut = k % size;  }
00044 
00045 #define HASH_2(k,size,idxOut)      \
00046           {  \
00047             int r = k % (size-13); \
00048             r = (r % 2) ? r : r+1; \
00049             *idxOut = r;           \
00050           }
00051 
00052 
00053 /*--------------------------------------------------------------
00054  * class structure
00055  *--------------------------------------------------------------*/
00056 typedef struct _hash_i_node_private Hash_i_Record;
00057 
00058 struct _hash_i_node_private
00059 {
00060   int key;
00061   int mark;
00062   int data;
00063 };
00064 
00065 
00066 struct _hash_i_dh
00067 {
00068   int size;     /* total slots in table */
00069   int count;      /* number of items inserted in table */
00070   int curMark;      /* used by Reset */
00071   Hash_i_Record *data;
00072 };
00073 
00074 
00075 /*--------------------------------------------------------------
00076  * class methods follow
00077  *--------------------------------------------------------------*/
00078 
00079 #undef __FUNC__
00080 #define __FUNC__ "Hash_i_dhCreate"
00081 void
00082 Hash_i_dhCreate (Hash_i_dh * h, int sizeIN)
00083 {
00084   START_FUNC_DH int i, size;
00085   Hash_i_Record *tmp2;
00086   struct _hash_i_dh *tmp;
00087 
00088   size = DEFAULT_TABLE_SIZE;
00089   if (sizeIN == -1)
00090     {
00091       sizeIN = size = DEFAULT_TABLE_SIZE;
00092     }
00093   tmp = (struct _hash_i_dh *) MALLOC_DH (sizeof (struct _hash_i_dh));
00094   CHECK_V_ERROR;
00095   *h = tmp;
00096   tmp->size = 0;
00097   tmp->count = 0;
00098   tmp->curMark = 0;
00099   tmp->data = NULL;
00100 
00101   /*
00102      determine initial hash table size.  If this is too small,
00103      it will be dynamically enlarged as needed by Hash_i_dhInsert()
00104      See "double hashing," p. 255, "Algorithms," Cormen, et. al.
00105    */
00106   while (size < sizeIN)
00107     size *= 2;      /* want table size to be a power of 2: */
00108   /* rule-of-thumb: ensure there's at least 10% padding */
00109   if ((size - sizeIN) < (.1 * size))
00110     {
00111       size *= 2.0;
00112     }
00113   tmp->size = size;
00114 
00115 
00116   /* allocate and zero the hash table */
00117   tmp2 = tmp->data =
00118     (Hash_i_Record *) MALLOC_DH (size * sizeof (Hash_i_Record));
00119   CHECK_V_ERROR;
00120   for (i = 0; i < size; ++i)
00121     {
00122       tmp2[i].key = -1;
00123       tmp2[i].mark = -1;
00124       /* "tmp2[i].data" needn't be initialized */
00125     }
00126 
00127 END_FUNC_DH}
00128 
00129 
00130 #undef __FUNC__
00131 #define __FUNC__ "Hash_i_dhDestroy"
00132 void
00133 Hash_i_dhDestroy (Hash_i_dh h)
00134 {
00135   START_FUNC_DH if (h->data != NULL)
00136     {
00137       FREE_DH (h->data);
00138       CHECK_V_ERROR;
00139     }
00140   FREE_DH (h);
00141   CHECK_V_ERROR;
00142 END_FUNC_DH}
00143 
00144 #undef __FUNC__
00145 #define __FUNC__ "Hash_i_dhReset"
00146 void
00147 Hash_i_dhReset (Hash_i_dh h)
00148 {
00149   START_FUNC_DH h->count = 0;
00150   h->curMark += 1;
00151 END_FUNC_DH}
00152 
00153 
00154 #undef __FUNC__
00155 #define __FUNC__ "Hash_i_dhLookup"
00156 int
00157 Hash_i_dhLookup (Hash_i_dh h, int key)
00158 {
00159   START_FUNC_DH int idx, inc, i, start;
00160   int curMark = h->curMark;
00161   int size = h->size;
00162   int retval = -1;
00163   Hash_i_Record *data = h->data;
00164 
00165   HASH_1 (key, size, &start) HASH_2 (key, size, &inc)
00166 /*printf("Hash_i_dhLookup:: key: %i  tableSize: %i start: %i  inc: %i\n", key, size, start, inc);
00167 */
00168     for (i = 0; i < size; ++i)
00169     {
00170       idx = (start + i * inc) % size;
00171 
00172 /* printf("   idx= %i\n", idx); */
00173 
00174       if (data[idx].mark != curMark)
00175   {
00176     break;    /* key wasn't found */
00177   }
00178       else
00179   {
00180     if (data[idx].key == key)
00181       {
00182         retval = data[idx].data;
00183         break;
00184       }
00185   }
00186     }
00187 END_FUNC_VAL (retval)}
00188 
00189 
00190 #undef __FUNC__
00191 #define __FUNC__ "Hash_i_dhInsert"
00192 void
00193 Hash_i_dhInsert (Hash_i_dh h, int key, int dataIN)
00194 {
00195   START_FUNC_DH int i, idx, inc, start, size;
00196   int curMark = h->curMark;
00197   Hash_i_Record *data;
00198   bool success = false;
00199 
00200   if (dataIN < 0)
00201     {
00202       sprintf (msgBuf_dh, "data = %i must be >= 0", dataIN);
00203       SET_V_ERROR (msgBuf_dh);
00204     }
00205 
00206   /* enlarge table if necessary */
00207   if (h->count >= 0.9 * h->size)
00208     {
00209       rehash_private (h);
00210       CHECK_V_ERROR;
00211     }
00212 
00213   size = h->size;
00214   data = h->data;
00215   h->count += 1;    /* for this insertion */
00216 
00217   HASH_1 (key, size, &start) HASH_2 (key, size, &inc)
00218 /*printf("Hash_i_dhInsert::  tableSize= %i  start= %i  inc= %i\n", size, start, inc);
00219 */
00220     for (i = 0; i < size; ++i)
00221     {
00222       idx = (start + i * inc) % size;
00223 
00224 /* printf("   idx= %i\n", idx);
00225 */
00226 
00227       /* check for previous insertion */
00228       if (data[idx].mark == curMark && data[idx].key == key)
00229   {
00230     sprintf (msgBuf_dh, "key,data= <%i, %i> already inserted", key,
00231        dataIN);
00232     SET_V_ERROR (msgBuf_dh);
00233   }
00234 
00235       if (data[idx].mark < curMark)
00236   {
00237     data[idx].key = key;
00238     data[idx].mark = curMark;
00239     data[idx].data = dataIN;
00240     success = true;
00241     break;
00242   }
00243     }
00244 
00245   if (!success)
00246     {       /* should be impossible to be here, I think . . . */
00247       sprintf (msgBuf_dh, "Failed to insert key= %i, data= %i", key, dataIN);
00248     }
00249 END_FUNC_DH}
00250 
00251 
00252 #undef __FUNC__
00253 #define __FUNC__ "rehash_private"
00254 void
00255 rehash_private (Hash_i_dh h)
00256 {
00257   START_FUNC_DH
00258     int i,
00259     old_size = h->size, new_size = old_size * 2, oldCurMark = h->curMark;
00260   Hash_i_Record *oldData = h->data, *newData;
00261 
00262   sprintf (msgBuf_dh, "rehashing; old_size= %i, new_size= %i", old_size,
00263      new_size);
00264   SET_INFO (msgBuf_dh);
00265 
00266   /* allocate new data table, and install it in the Hash_i_dh object;
00267      essentially, we reinitialize the hash object.
00268    */
00269   newData = (Hash_i_Record *) MALLOC_DH (new_size * sizeof (Hash_i_Record));
00270   CHECK_V_ERROR;
00271   for (i = 0; i < new_size; ++i)
00272     {
00273       newData[i].key = -1;
00274       newData[i].mark = -1;
00275     }
00276   h->size = new_size;
00277   h->data = newData;
00278   h->count = 0;
00279   h->curMark = 0;
00280 
00281   for (i = h->count; i < new_size; ++i)
00282     {
00283       newData[i].key = -1;
00284       newData[i].mark = -1;
00285     }
00286 
00287   /* insert <key, data> pairs from old table to new table;
00288      wouldn't have been called) it's simplest to sweep through
00289      the old table.
00290    */
00291   for (i = 0; i < old_size; ++i)
00292     {
00293       if (oldData[i].mark == oldCurMark)
00294   {
00295     Hash_i_dhInsert (h, oldData[i].key, oldData[i].data);
00296     CHECK_V_ERROR;
00297   }
00298     }
00299 
00300   FREE_DH (oldData);
00301   CHECK_V_ERROR;
00302 END_FUNC_DH}
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines