libStatGen Software  1
BasicHash.cpp
00001 /*
00002  *  Copyright (C) 2010  Regents of the University of Michigan
00003  *
00004  *   This program is free software: you can redistribute it and/or modify
00005  *   it under the terms of the GNU General Public License as published by
00006  *   the Free Software Foundation, either version 3 of the License, or
00007  *   (at your option) any later version.
00008  *
00009  *   This program is distributed in the hope that it will be useful,
00010  *   but WITHOUT ANY WARRANTY; without even the implied warranty of
00011  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00012  *   GNU General Public License for more details.
00013  *
00014  *   You should have received a copy of the GNU General Public License
00015  *   along with this program.  If not, see <http://www.gnu.org/licenses/>.
00016  */
00017 
00018 #include "BasicHash.h"
00019 #include "Error.h"
00020 
00021 #include <stdio.h>
00022 
00023 BasicHash::BasicHash(int startsize)
00024 {
00025     count = 0;
00026     size  = startsize;
00027     mask  = startsize - 1;
00028 
00029     // In this implementation, the size of hash tables must be a power of two
00030     if (startsize & mask)
00031         error("BasicHash: Hash table size must be a power of two.\n");
00032 
00033     objects = new void * [size];
00034     keys    = new unsigned int [size];
00035 
00036     for (unsigned int i = 0; i < size; i++)
00037     {
00038         objects[i] = NULL;
00039     }
00040 };
00041 
00042 BasicHash::~BasicHash()
00043 {
00044     delete [] objects;
00045     delete [] keys;
00046 }
00047 
00048 void BasicHash::Clear()
00049 {
00050 //   printf("Clearing...\n");
00051 
00052     count = 0;
00053 
00054     if (size > 16)
00055         SetSize(16);
00056 
00057     for (unsigned int i = 0; i < size; i++)
00058         objects[i] = NULL;
00059 }
00060 
00061 void BasicHash::SetSize(int newsize)
00062 {
00063     int newmask = newsize - 1;
00064 
00065     void     ** newobjects = new void * [newsize];
00066     unsigned int * newkeys = new unsigned int [newsize];
00067 
00068     for (int i = 0; i < newsize; i++)
00069     {
00070         newobjects[i] = NULL;
00071     }
00072 
00073     if (count)
00074         for (unsigned int i = 0; i < size; i++)
00075             if (objects[i] != NULL)
00076             {
00077                 unsigned int key = keys[i];
00078                 unsigned int h   = key & newmask;
00079 
00080                 while (newobjects[h] != NULL && newkeys[h] != h)
00081                     h = (h + 1) & newmask;
00082 
00083                 newkeys[h] = key;
00084                 newobjects[h] = objects[i];
00085             }
00086 
00087     delete [] objects;
00088     delete [] keys;
00089 
00090     objects = newobjects;
00091     keys = newkeys;
00092     size = newsize;
00093     mask = newmask;
00094 }
00095 
00096 int BasicHash::Add(int key, void * object)
00097 {
00098     if (count * 2 > size)
00099         Grow();
00100 
00101     unsigned int h = Iterate(key);
00102 
00103     while ((objects[h] != NULL) && (objects[h] != object))
00104         h = ReIterate(key, h);
00105 
00106     if (objects[h] == NULL)
00107     {
00108 //      printf("At position %d, inserted %x\n", h, key);
00109         keys[h] = key;
00110         count++;
00111     }
00112 
00113     objects[h] = object;
00114 
00115     return h;
00116 }
00117 
00118 int BasicHash::Find(int key)
00119 {
00120     int h = Iterate(key);
00121 
00122     return objects[h] == NULL ? -1 : h;
00123 }
00124 
00125 int BasicHash::Rehash(int key, int h)
00126 {
00127     h = ReIterate(key, h);
00128 
00129     return objects[h] == NULL ? -1 : h;
00130 }
00131 
00132 void BasicHash::Delete(unsigned int index)
00133 {
00134     if (index >= size || objects[index] == NULL)
00135         return;
00136 
00137     objects[index] = NULL;
00138     count--;
00139 
00140     if (count * 8 < size && size > 32)
00141         Shrink();
00142     else
00143     {
00144         // rehash the next entries until we find empty slot
00145         index = (index + 1) & mask;
00146 
00147         while (objects[index] != NULL)
00148         {
00149             if ((keys[index] & mask) != index)
00150             {
00151                 unsigned int h = Iterate(keys[index]);
00152 
00153                 while ((objects[h] != NULL) && (objects[h] != objects[index]))
00154                     h = ReIterate(keys[index], h);
00155 
00156                 if (h != (unsigned int) index)
00157                 {
00158                     keys[h] = keys[index];
00159                     objects[h] = objects[index];
00160                     objects[index] = NULL;
00161                 }
00162             }
00163 
00164             index = (index + 1) & mask;
00165         }
00166     }
00167 }
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends