swcsa/utils/hash.h

   1 \r
   2 /* DYNAMIC END-TAGGED DENSE CODE. -- \r
   3 A dynamic word-based byte oriented compressor for text files based on \r
   4 dynamic End-Tagged Dense Code.\r
   5 \r
   6 Brisaboa, N. R., Fariña, A., Navarro, G., Paramá, J. R. \r
   7 Simple, Fast, and Efficient Natural Language Adaptive Compression. \r
   8 11th International Symposium on String Processing and Information Retrieval (SPIRE'04) - LNCS 3246. A. Apostolico, M. Melucci (Ed.), pp. 230-241. \r
   9 Padova (Italia), 2004. \r
  10 \r
  11 Copyright (C) 2005 Antonio Fariña.\r
  12 \r
  13 This program is free software; you can redistribute it and/or\r
  14 modify it under the terms of the GNU General Public License\r
  15 as published by the Free Software Foundation; either version 2\r
  16 of the License, or (at your option) any later version.\r
  17 \r
  18 This program is distributed in the hope that it will be useful,\r
  19 but WITHOUT ANY WARRANTY; without even the implied warranty of\r
  20 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the\r
  21 GNU General Public License for more details.\r
  22 \r
  23 You should have received a copy of the GNU General Public License\r
  24 along with this program; if not, write to the Free Software\r
  25 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.\r
  26 \r
  27 Author's contact: Antonio Fariña, Dept. of Computer Science, University of\r
  28 A Coruña. Campus de Elviña s/n. Spain  fari@udc.es\r
  29 */\r
  30 \r
  31 \r
  32 /*-----------------------------------------------------------------------\r
  33  Hash: Definition of HashTable class (Linear Hash)\r
  34  ------------------------------------------------------------------------*/\r
  35 #ifndef HASH_INCLUDED\r
  36 #define HASH_INCLUDED\r
  37  \r
  38 #include <string.h>\r
  39 #include <stdlib.h>\r
  40 #include <math.h>\r
  41 //#include <malloc.h>\r
  42 \r
  43 #include "MemoryManager.h"\r
  44 \r
  45 #define JUMP 101                 //jump done when a collision appears\r
  46 #define OCUP_HASH 1.5            //index of occupation of the hash table\r
  47 #define SMALL_PRIME 1009 // a small prime number, used to compute a hash function\r
  48 #define SEED    1159241\r
  49 /* Type definitions */\r
  50 \r
  51 #define MIN(a,b) (a < b) ? a : b\r
  52 \r
  53 struct hashNode {\r
  54           unsigned char *word;\r
  55           unsigned long len;\r
  56           unsigned long posInVoc;         //positon of the canonical word in vector posInHT\r
  57 };\r
  58 typedef struct hashNode t_hashNode;\r
  59 \r
  60 struct hashStr {\r
  61         t_hashNode *hash;                 /* the slots in the hash table        */\r
  62         unsigned long SIZE_HASH;   /* # entries in the hash table    */\r
  63         unsigned long NumElem;    /* # elements already added to the hash table*/\r
  64         MemoryManager _memMgr;    /* Holds dynamic memory allocation for words. */      \r
  65 };\r
  66 \r
  67 typedef struct hashStr *t_hash;\r
  68 \r
  69 // private:\r
  70 \r
  71         unsigned long NearestPrime (unsigned long n);\r
  72         unsigned long hashFunction (const unsigned char *aWord, unsigned int len, unsigned long sizeHash);\r
  73 \r
  74 // public:\r
  75         \r
  76         t_hash initialize_hash (unsigned long sizeVoc);\r
  77         \r
  78         void insertElement (t_hash h, const unsigned char *aWord, register unsigned long len,\r
  79                                                               register unsigned long *addr);\r
  80         unsigned long search (t_hash h, const unsigned char *aWord, register unsigned len,\r
  81                                                                   unsigned long *returnedAddr);\r
  82         unsigned long inHashTable (t_hash h, const unsigned char *aWord, register unsigned len,\r
  83                                                                   unsigned long *returnedAddr);\r
  84         void destroy_hash (t_hash hash);\r
  85         \r
  86         int strcomp(const unsigned char *s1, const unsigned char *s2, register unsigned long ws1, unsigned long ws2);\r
  87 \r
  88         int strcompL(const byte *s1, const byte *s2, register ulong ws1, register ulong ws2);\r
  89 \r
  90 \r
  91 #endif\r