1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
|
/******************************************************************************
IrstLM: IRST Language Model Toolkit
Copyright (C) 2006 Marcello Federico, ITC-irst Trento, Italy
This library is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
License as published by the Free Software Foundation; either
version 2.1 of the License, or (at your option) any later version.
This library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
Lesser General Public License for more details.
You should have received a copy of the GNU Lesser General Public
License along with this library; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
******************************************************************************/
#ifndef MF_HTABLE_H
#define MF_HTABLE_H
#include <iostream>
#define Prime1 37
#define Prime2 1048583
#define BlockSize 100
// Fast arithmetic, relying on powers of 2,
// and on pre-processor concatenation property
typedef struct{
char* key;
char* next; // secret from user
}entry;
typedef unsigned int address;
typedef enum {HT_FIND, //!< search: find an entry
HT_ENTER, //!< search: enter an entry
HT_INIT, //!< scan: start scan
HT_CONT //!< scan: continue scan
} HT_ACTION;
typedef enum {
STR, //!< string
STRPTR, //!< pointer to string
INT, //!< pointer to int
INTPTR //!< pointer to pointer to int
}HTYPE;
//! Hash Table for strings
class htable {
int size; //!< table size
int keylen; //!< key length
HTYPE htype; //!< type of entry pointer
entry **table; //!< hash table
int scan_i; //!< scan support
entry *scan_p; //!< scan support
// statistics
long keys; //!< # of entries
long accesses; //!< # of accesses
long collisions; //!< # of collisions
mempool *memory; //!< memory pool
size_t (*keylenfunc)(const char*); //!< function computing key length
address (*hashfunc)(const char*); //!< hash function
int (*compfunc)(const char*, const char*); //!< comparison function
public:
//! Creates an hash table
htable(int n,int kl=0,HTYPE ht=STRPTR,size_t (*klf)(const char* )=NULL);
//! Destroys an and hash table
~htable();
//! Computes the hash function
address Hash(char *key){
switch (htype){
case INT:case INTPTR: return HashInt(key);
break;
case STR:case STRPTR: return HashStr(key);
default: exit(1);
}
};
address HashInt(char *key);
address HashStr(char *key);
//! Compares the keys of two entries
int Comp(char *Key1,char *Key2){
switch (htype){
case INT:case INTPTR: return CompInt(Key1,Key2);
break;
case STR:case STRPTR: return CompStr(Key1,Key2);
default: exit(1);
};
}
int CompInt(char *Key1,char *Key2);
int CompStr(char *Key1,char *Key2);
//! Searches for an item
char *search(char *item, HT_ACTION action);
//! Scans the content
char *scan(HT_ACTION action);
//! Prints statistics
void stat();
//! Print a map of memory use
void map(std::ostream& co=std::cout, int cols=80);
//! Returns amount of used memory
int used(){return
size * sizeof(entry **) +
memory->used();};
};
#endif
|
