IFPACK Development
Hash_dh.c
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_dh.h"
00031 #include "Parser_dh.h"
00032 #include "Mem_dh.h"
00033 
00034 static void Hash_dhInit_private (Hash_dh h, int s);
00035 
00036 #define CUR_MARK_INIT  -1
00037 
00038 
00039 struct _hash_node_private
00040 {
00041   int key;
00042   int mark;
00043   HashData data;
00044 };
00045 
00046 
00047 #undef __FUNC__
00048 #define __FUNC__ "Hash_dhCreate"
00049 void
00050 Hash_dhCreate (Hash_dh * h, int size)
00051 {
00052   START_FUNC_DH
00053     struct _hash_dh *tmp =
00054     (struct _hash_dh *) MALLOC_DH (sizeof (struct _hash_dh));
00055   CHECK_V_ERROR;
00056   *h = tmp;
00057   tmp->size = 0;
00058   tmp->count = 0;
00059   tmp->curMark = CUR_MARK_INIT + 1;
00060   tmp->data = NULL;
00061 
00062   Hash_dhInit_private (*h, size);
00063   CHECK_V_ERROR;
00064 END_FUNC_DH}
00065 
00066 #undef __FUNC__
00067 #define __FUNC__ "Hash_dhDestroy"
00068 void
00069 Hash_dhDestroy (Hash_dh h)
00070 {
00071   START_FUNC_DH if (h->data != NULL)
00072     {
00073       FREE_DH (h->data);
00074       CHECK_V_ERROR;
00075     }
00076   FREE_DH (h);
00077   CHECK_V_ERROR;
00078 END_FUNC_DH}
00079 
00080 #undef __FUNC__
00081 #define __FUNC__ "Hash_dhReset"
00082 void
00083 Hash_dhReset (Hash_dh h)
00084 {
00085   START_FUNC_DH h->count = 0;
00086   h->curMark += 1;
00087 END_FUNC_DH}
00088 
00089 #undef __FUNC__
00090 #define __FUNC__ "Hash_dhInit_private"
00091 void
00092 Hash_dhInit_private (Hash_dh h, int s)
00093 {
00094   START_FUNC_DH int i;
00095   int size = 16;
00096   HashRecord *data;
00097 
00098   /* want table size to be a power of 2: */
00099   while (size < s)
00100     size *= 2;
00101   /* rule-of-thumb: ensure there's some padding */
00102   if ((size - s) < (.1 * size))
00103     {
00104       size *= 2.0;
00105     }
00106   h->size = size;
00107 
00108 /*
00109   sprintf(msgBuf_dh, "requested size = %i; allocated size = %i", s, size); 
00110   SET_INFO(msgBuf_dh);
00111 */
00112 
00113   /* allocate and zero the hash table */
00114   data = h->data = (HashRecord *) MALLOC_DH (size * sizeof (HashRecord));
00115   CHECK_V_ERROR;
00116   for (i = 0; i < size; ++i)
00117     {
00118       data[i].key = -1;
00119       data[i].mark = -1;
00120     }
00121 END_FUNC_DH}
00122 
00123 #undef __FUNC__
00124 #define __FUNC__ "Hash_dhLookup"
00125 HashData *
00126 Hash_dhLookup (Hash_dh h, int key)
00127 {
00128   START_FUNC_DH int i, start;
00129   int curMark = h->curMark;
00130   int size = h->size;
00131   HashData *retval = NULL;
00132   HashRecord *data = h->data;
00133 
00134   HASH_1 (key, size, &start) for (i = 0; i < size; ++i)
00135     {
00136       int tmp, idx;
00137       HASH_2 (key, size, &tmp) idx = (start + i * tmp) % size;
00138       if (data[idx].mark != curMark)
00139     {
00140       break;        /* key wasn't found */
00141     }
00142       else
00143     {
00144       if (data[idx].key == key)
00145         {
00146           retval = &(data[idx].data);
00147           break;
00148         }
00149     }
00150     }
00151 END_FUNC_VAL (retval)}
00152 
00153 
00154 /* 
00155   TODO: (1) check for already-inserted  (done?)
00156         (2) rehash, if table grows too large
00157 */
00158 #undef __FUNC__
00159 #define __FUNC__ "Hash_dhInsert"
00160 void
00161 Hash_dhInsert (Hash_dh h, int key, HashData * dataIN)
00162 {
00163   START_FUNC_DH int i, start, size = h->size;
00164   int curMark = h->curMark;
00165   HashRecord *data;
00166 
00167   data = h->data;
00168 
00169   /* check for overflow */
00170   h->count += 1;
00171   if (h->count == h->size)
00172     {
00173       SET_V_ERROR ("hash table overflow; rehash need implementing!");
00174     }
00175 
00176   HASH_1 (key, size, &start) for (i = 0; i < size; ++i)
00177     {
00178       int tmp, idx;
00179       HASH_2 (key, size, &tmp) idx = (start + i * tmp) % size;
00180       if (data[idx].mark < curMark)
00181     {
00182       data[idx].key = key;
00183       data[idx].mark = curMark;
00184       memcpy (&(data[idx].data), dataIN, sizeof (HashData));
00185       break;
00186     }
00187     }
00188 END_FUNC_DH}
00189 
00190 #undef __FUNC__
00191 #define __FUNC__ "Hash_dhPrint"
00192 void
00193 Hash_dhPrint (Hash_dh h, FILE * fp)
00194 {
00195   START_FUNC_DH int i, size = h->size;
00196   int curMark = h->curMark;
00197   HashRecord *data = h->data;
00198 
00199 
00200   fprintf (fp, "\n--------------------------- hash table \n");
00201   for (i = 0; i < size; ++i)
00202     {
00203       if (data[i].mark == curMark)
00204     {
00205       fprintf (fp, "key = %2i;  iData = %3i;  fData = %g\n",
00206            data[i].key, data[i].data.iData, data[i].data.fData);
00207     }
00208     }
00209   fprintf (fp, "\n");
00210 END_FUNC_DH}
 All Classes Files Functions Variables Enumerations Friends