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
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
11 Copyright (C) 2005 Antonio Fariña.
\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
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
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
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
32 /*-----------------------------------------------------------------------
\r
33 Hash: Definition of HashTable class (Linear Hash)
\r
34 ------------------------------------------------------------------------*/
\r
35 #ifndef HASH_INCLUDED
\r
36 #define HASH_INCLUDED
\r
43 #include "MemoryManager.h"
\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
51 #define MIN(a,b) (a < b) ? a : b
\r
54 unsigned char *word;
\r
56 unsigned long posInVoc; //positon of the canonical word in vector posInHT
\r
58 typedef struct hashNode t_hashNode;
\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
67 typedef struct hashStr *t_hash;
\r
71 unsigned long NearestPrime (unsigned long n);
\r
72 unsigned long hashFunction (const unsigned char *aWord, unsigned int len, unsigned long sizeHash);
\r
76 t_hash initialize_hash (unsigned long sizeVoc);
\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
86 int strcomp(const unsigned char *s1, const unsigned char *s2, register unsigned long ws1, unsigned long ws2);
\r
88 int strcompL(const byte *s1, const byte *s2, register ulong ws1, register ulong ws2);
\r