swcsa/utils/hash.c

   1
   2 /* DYNAMIC END-TAGGED DENSE CODE. --
   3 A dynamic word-based byte oriented compressor for text files based on
   4 dynamic End-Tagged Dense Code.
   5
   6 Brisaboa, N. R., Faria, A., Navarro, G., Param, J. R.
   7 Simple, Fast, and Efficient Natural Language Adaptive Compression.
   8 11th International Symposium on String Processing and Information Retrieval (SPIRE'04) - LNCS 3246. A. Apostolico, M. Melucci (Ed.), pp. 230-241.
   9 Padova (Italia), 2004.
  10
  11 Copyright (C) 2005 Antonio Faria.
  12
  13 This program is free software; you can redistribute it and/or
  14 modify it under the terms of the GNU General Public License
  15 as published by the Free Software Foundation; either version 2
  16 of the License, or (at your option) any later version.
  17
  18 This program is distributed in the hope that it will be useful,
  19 but WITHOUT ANY WARRANTY; without even the implied warranty of
  20 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  21 GNU General Public License for more details.
  22
  23 You should have received a copy of the GNU General Public License
  24 along with this program; if not, write to the Free Software
  25 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  26
  27 Author's contact: Antonio Faria, Dept. of Computer Science, University of
  28 A Corua. Campus de Elvia s/n. Spain  fari@udc.es
  29 */
  30
  31 /*-----------------------------------------------------------------------
  32  Hash: Definition of HashTable class (Linear Hash)
  33  ------------------------------------------------------------------------*/
  34
  35 #include "hash.h"
  36
  37 #include <stdio.h>
  38 #include <string.h>
  39 #include <stdlib.h>
  40
  41
  42 /*-----------------------------------------------------------------
  43  Initilization of data structures used by the hashTable
  44  ---------------------------------------------------------------- */
  45 t_hash initialize_hash (unsigned long sizeVoc) {
  46         t_hash h;
  47         unsigned long i;
  48
  49         h = (t_hash) malloc(sizeof(struct hashStr));
  50         h->SIZE_HASH = (unsigned long) (OCUP_HASH * sizeVoc);
  51         h->SIZE_HASH = NearestPrime(h->SIZE_HASH);
  52         h->hash = (t_hashNode *) malloc(h->SIZE_HASH * sizeof(t_hashNode));
  53         h->NumElem = 0;
  54
  55         //creates the memory manager that is used to reserve small pieces of memory (for words)
  56         h->_memMgr=createMemoryManager();
  57
  58
  59         for (i = 0; i < h->SIZE_HASH; i++)    {
  60                 h->hash[i].word = NULL;
  61                 h->hash[i].len = 0;
  62                 h->hash[i].posInVoc = 0;
  63         }
  64         printf("\nHash Table initilized with: %lu elements\n",h->SIZE_HASH);
  65
  66         return h;
  67 }
  68
  69
  70 /*------------------------------------------------------------------
  71  Find the nearest prime number over n.
  72  ---------------------------------------------------------------- */
  73 unsigned long NearestPrime(unsigned long n)
  74 {
  75     long position;  /* the prime number being sought */
  76     long index;
  77
  78     for (position = n; ; position++)
  79     {
  80         // checks if those values from 2 to $\sqrt{m}$ can be factors of $m$ */
  81         for (index = 2; index <= (long) sqrt((double) position) && position % index != 0; index++) ;
  82
  83         if (position % index != 0)  /* No factors in that range, therefore a prime number was found */
  84         {
  85             break;
  86         }
  87     }
  88     return position;
  89 }
  90
  91
  92
  93 /*-----------------------------------------------------------------------
  94  Computes a hash function over a string "aWord", it returns the position
  95  where "aWord" should go in the hash table if no collision ocurrs.
  96  ---------------------------------------------------------------------*/
  97 unsigned long hashFunction (const unsigned char *aWord, unsigned int len, unsigned long sizeHash)
  98 {
  99     char        c;
 100     register unsigned int h;
 101     register unsigned long last;
 102     last=((unsigned long) aWord) +len -1;
 103
 104
 105     h = SEED;
 106     //last=aWord+len;
 107
 108     for( ; ((unsigned long) aWord <=last ) ; )
 109     //for(c=*aWord; (aWord++)<last ;  )
 110     {
 111         c=*(aWord++);
 112                 //c=*aWord;
 113                 h ^= ( (h << 5) + c + (h >> 2) );
 114     }
 115     return((unsigned int)((h&0x7fffffff) % sizeHash));
 116 }
 117
 118
 119 /*-----------------------------------------------------------------------
 120   compares two strings
 121  ---------------------------------------------------------------------*/
 122
 123 /* Author J. Zobel, April 2001.
 124         http://www.seg.rmit.edu.au/code/zwh-ipl/
 125    Permission to use this code is freely granted, provided that this
 126    statement is retained. */
 127
 128
 129
 130  int strcomp(const unsigned char *s1, const unsigned char *s2, register unsigned long ws1, unsigned long ws2) {
 131          if (ws1 !=ws2) {
 132                         return -1;
 133          }
 134
 135          {  register unsigned long iters;
 136                  iters=1;
 137             while( iters<ws1 && *s1 == *s2 )
 138             {
 139                         s1++;
 140                         s2++;
 141                         iters++;
 142             }
 143             //fprintf(stderr,"\nDevuelve [%d]",*s1-*s2);
 144             return( *s1-*s2 );
 145          }
 146 }
 147
 148 inline int strcomp3(const unsigned char *s1, const unsigned char *s2, unsigned long ws1, unsigned long ws2) {
 149
 150          if (ws1 !=ws2) {
 151                         return -1;
 152          }
 153
 154          {  register unsigned long iters;
 155             register unsigned long end;
 156             end = MIN(ws1,ws2);
 157                  iters=1;
 158             while( iters<end && *s1 == *s2 )
 159             {
 160                         s1++;
 161                         s2++;
 162                         iters++;
 163             }
 164             //fprintf(stderr,"\nDevuelve [%d]",*s1-*s2);
 165             return( *s1-*s2 );
 166          }
 167 }
 168
 169
 170 /* Author J. Zobel, April 2001.
 171         http://www.seg.rmit.edu.au/code/zwh-ipl/
 172    Permission to use this code is freely granted, provided that this
 173    statement is retained. */
 174
 175 //int strcomp(const unsigned char *s1, const unsigned char *s2, unsigned long ws) {
 176 //    register unsigned long i;
 177 //    i=0;
 178 //    while( i < ws-1 && *s1 == *s2 )*/
 179 //    {
 180 //                      s1++;
 181 //                      s2++;
 182 //                      i++;
 183 //    }
 184 //    return( *s1-*s2 );
 185 //}
 186
 187 //int strcompL(const byte *s1, const byte *s2, register ulong ws1, register ulong ws2) {
 188 //      register ulong iters = 1;
 189 //
 190 //      while( iters<ws1 && *s1 == *s2 ){
 191 //              s1++;
 192 //              s2++;
 193 //              iters++;
 194 //      }
 195 //        // so     iters == ws1   OR   *s1 != *s2
 196 //      if (ws1 == iters) {
 197 //                      if (ws2 == ws1)
 198 //                              return 0;  // s1 equals to s2
 199 //                      else
 200 //                              return -1;   // s1 < s2
 201 //      }
 202 //      else { //(ws1 > iters) so s1 != s2
 203 //              return( *s1-*s2);
 204 //      }
 205 //}
 206
 207
 208 //permits to compare 2 strings of len ws1 and ws2 that do not end in '\0'
 209 int strcompL(const byte *s1, const byte *s2, register ulong ws1, register ulong ws2) {
 210         register ulong iters = 0;
 211
 212         while( iters<ws1 && iters<ws2 && *s1 == *s2 ){
 213                 s1++;
 214                 s2++;
 215                 iters++;
 216         }
 217
 218         if (ws1 == iters) {
 219                         if (ws2 == ws1)
 220                                 return 0;  // s1 equals to s2
 221                         else
 222                                 return -1;   // w1 < w2  and  *s1_i == *s2_i for i=0 to iters-1
 223         }
 224         else
 225         if (ws2 == iters) {
 226                         if (ws2 == ws1)
 227                                 return 0;  // s1 equals to s2
 228                         else
 229                                 return +1;   // w2 < w1  and  *ws1 is '\0'
 230         }
 231         else { //*s1 != *s2
 232                 return (*s1-*s2);
 233         }
 234
 235 }
 236
 237
 238 /*-----------------------------------------------------------------------
 239  Insert a new word in a position of the hashTable (position previously computed)
 240  ---------------------------------------------------------------------*/
 241 void insertElement (t_hash h, const unsigned char *aWord, register unsigned long len, register unsigned long *addr) {
 242     //fprintf(stderr,"\n Entra en la funcin [%s], [%ld]",aWord, len);
 243
 244         if(h->NumElem >= h->SIZE_HASH -1)   //loses 1 slot, but ensures that "search function" does not enter an infinity loop
 245         {
 246                 printf("\n\nHash table full!! Change size and recompile !\n");
 247                 exit(1);
 248         }
 249
 250     getMemoryBlock(h->_memMgr,( byte **)&(h->hash[*addr].word),len+1);
 251     //fprintf(stderr,"\n tras obter memoria");
 252
 253         strncpy ((char *) h->hash[*addr].word, (char *)aWord, len);
 254
 255         h->hash[*addr].word[len]='\0';
 256         h->hash[*addr].len =len;
 257         h->hash[*addr].posInVoc = h->NumElem;
 258         h->NumElem++;
 259
 260         //fprintf(stderr,"\n####inserted word [%s] ",h->hash[*addr].word);
 261
 262         //return *addr;
 263 }
 264
 265 /*-----------------------------------------------------------------------
 266  Search for a word in the hash table and returns its position in the
 267  vocabulary. It returns the next "available" position in the vocabulary,
 268  if the word is not in the hash table. That is: a "0-node" position.
 269  It also returns -using attribute returnedAddr- the position where word
 270  was found (or where it should go if it was inserted in next "insert call".
 271  -----------------------------------------------------------------------*/
 272 unsigned long search (t_hash h, const unsigned char *aWord, register unsigned len,
 273                                                                  unsigned long *returnedAddr){
 274
 275         register unsigned long addr, Saddr;
 276
 277         //fprintf(stderr,"\n searching for  [%s], [%d], sizehash= %ld",aWord,len,h->SIZE_HASH);
 278         addr = hashFunction(aWord,len, h->SIZE_HASH);
 279         Saddr = addr;
 280
 281         t_hashNode *hash;
 282         hash = h->hash;
 283
 284         while((hash[addr].word  != NULL)&&((strcomp(hash[addr].word, aWord,  hash[addr].len, len)) != 0))  {
 285                 //fprintf(stderr,"\nComprueba [%s], [%d]",hash[addr].word,strcomp(hash[addr].word, aWord, len));
 286                 addr = ((addr + JUMP) % h->SIZE_HASH);
 287         }
 288
 289         *returnedAddr = addr;
 290
 291         if(hash[addr].word  == NULL) {
 292                 return h->NumElem;                              //Word was not found
 293         }
 294         else {
 295                 return h->hash[addr].posInVoc; //Word was found in this position in the vocabulary
 296         }
 297 }
 298
 299
 300
 301 /*-----------------------------------------------------------------------
 302   Tells if a word appears or not in the hash table.
 303  -----------------------------------------------------------------------*/
 304 unsigned long inHashTable (t_hash h, const unsigned char *aWord, register unsigned len, unsigned long *returnedAddr){
 305
 306         unsigned long searched;
 307         unsigned long nothing;
 308         searched = search(h,aWord,len,&nothing);
 309         *returnedAddr=nothing;
 310         return (searched < (h->NumElem) );
 311 }
 312
 313 /*------------------------------------------------------------------
 314  Destructor method
 315  ------------------------------------------------------------------ */
 316 void destroy_hash (t_hash hash){
 317         unsigned long mem=0;
 318         mem += sizeof(struct hashStr) + hash->SIZE_HASH * sizeof(t_hashNode);
 319         free(hash->hash);
 320         destroyMemoryManager(hash->_memMgr); //frees words and variants
 321 //      free(hash->_memMgr);
 322         free(hash);
 323         printf("\n[destroying hash table]...Freed %ld bytes... RAM", mem);
 324 }
 325
 326
 327
 328
 329 /*------------------------------------------------------------------
 330  main, to make unit proofs
 331  ------------------------------------------------------------------ */
 332 /*
 333 int main(int argc, char* argv[])
 334 {   byte a[10]= "word1";
 335         byte b[10]= "word2";
 336         byte c[10]= "word3";
 337         byte d[10]= "word4";
 338         byte e[10]= "word5";
 339         byte f[10]= "word6";
 340         byte * w;
 341         unsigned int size;
 342         unsigned long i,addrInTH;
 343
 344         t_hash hash;
 345
 346         _memMgr=createMemoryManager();
 347
 348         hash = initialize_hash (2);
 349
 350         w=a;
 351         i = search (hash,w, strlen(w), &addrInTH );
 352         insertElement (hash, w, strlen(w), &addrInTH);
 353         fprintf(stderr,"\n i = %ld, addrInTh = %ld ",i,addrInTH);
 354         fprintf(stderr,"\n word in hash[%ld]= %s , freq = %ld, posinvoc =%ld",addrInTH, hash->hash[addrInTH].word, hash->hash[addrInTH].freq, hash->hash[addrInTH].posInVoc);
 355
 356         w=b;
 357         i = search (hash,w, strlen(w), &addrInTH );
 358         insertElement (hash, w, strlen(w), &addrInTH);
 359         fprintf(stderr,"\n i = %ld, addrInTh = %ld ",i,addrInTH);
 360         fprintf(stderr,"\n word in hash[%ld]= %s , freq = %ld, posinvoc =%ld",addrInTH, hash->hash[addrInTH].word, hash->hash[addrInTH].freq, hash->hash[addrInTH].posInVoc);
 361
 362         w=c;
 363         i = search (hash,w, strlen(w), &addrInTH );
 364         insertElement (hash, w, strlen(w), &addrInTH);
 365         fprintf(stderr,"\n i = %ld, addrInTh = %ld ",i,addrInTH);
 366         fprintf(stderr,"\n word in hash[%ld]= %s , freq = %ld, posinvoc =%ld",addrInTH, hash->hash[addrInTH].word, hash->hash[addrInTH].freq, hash->hash[addrInTH].posInVoc);
 367
 368         w=d;
 369         i = search (hash,w, strlen(w), &addrInTH );
 370         insertElement (hash, w, strlen(w), &addrInTH);
 371         fprintf(stderr,"\n i = %ld, addrInTh = %ld ",i,addrInTH);
 372         fprintf(stderr,"\n word in hash[%ld]= %s , freq = %ld, posinvoc =%ld",addrInTH, hash->hash[addrInTH].word, hash->hash[addrInTH].freq, hash->hash[addrInTH].posInVoc);
 373
 374 //      w=e;
 375 //      i = search (hash,w, strlen(w), &addrInTH );
 376 //      insertElement (hash, w, strlen(w), &addrInTH);
 377 //      fprintf(stderr,"\n i = %ld, addrInTh = %ld ",i,addrInTH);
 378 //      fprintf(stderr,"\n word in hash[%ld]= %s , freq = %ld, posinvoc =%ld",addrInTH, hash->hash[addrInTH].word, hash->hash[addrInTH].freq, hash->hash[addrInTH].posInVoc);
 379
 380 //      w=f;
 381 //      i = search (hash,w, strlen(w), &addrInTH );
 382 //      insertElement (hash, w, strlen(w), &addrInTH);
 383 //      fprintf(stderr,"\n i = %ld, addrInTh = %ld ",i,addrInTH);
 384 //      fprintf(stderr,"\n word in hash[%ld]= %s , freq = %ld, posinvoc =%ld",addrInTH, hash->hash[addrInTH].word, hash->hash[addrInTH].freq, hash->hash[addrInTH].posInVoc);
 385
 386         fprintf(stderr,"\n in: %s  hash ? = %d",a,inHashTable(hash,a,strlen(a)) );
 387         fprintf(stderr,"\n in: %s  hash ? = %d",e, inHashTable(hash,e,strlen(e)) );
 388         fprintf(stderr,"\n in: %s  hash ? = %d",b, inHashTable(hash,b,strlen(b)) );
 389
 390         destroy_hash(hash);
 391         destroyMemoryManager(_memMgr);
 392         printf("\n\n");
 393 }
 394 */