00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023 #ifndef MF_HTABLE_H
00024 #define MF_HTABLE_H
00025
00026 using namespace std;
00027
00028 #include <iostream>
00029 #include <string>
00030 #include <cstring>
00031 #include "mempool.h"
00032
00033 #define Prime1 37
00034 #define Prime2 1048583
00035 #define BlockSize 100
00036
00037 typedef unsigned int address;
00038
00039
00040
00041
00042 template <class T>
00043 struct entry {
00044 T key;
00045 entry* next;
00046 };
00047
00048
00049 typedef enum {HT_FIND,
00050 HT_ENTER,
00051 HT_INIT,
00052 HT_CONT
00053 } HT_ACTION;
00054
00056 template <class T>
00057 class htable
00058 {
00059 int size;
00060 int keylen;
00061 entry<T> **table;
00062 int scan_i;
00063 entry<T> *scan_p;
00064
00065 long keys;
00066 long accesses;
00067 long collisions;
00068
00069 mempool *memory;
00070
00071 public:
00072
00074 htable(int n,int kl=0);
00075
00077 ~htable();
00078
00079 void set_keylen(int kl);
00080
00082 address Hash(const T key);
00083
00085 int Comp(const T Key1, const T Key2);
00086
00088 T find(T item);
00089 T insert(T item);
00090
00092 T scan(HT_ACTION action);
00093
00095 void stat();
00096
00098 void map(std::ostream& co=std::cout, int cols=80);
00099
00101 int used() {
00102 return size * sizeof(entry<T> **) + memory->used();
00103 }
00104
00105 };
00106
00107
00108
00109 template <class T>
00110 htable<T>::htable(int n,int kl)
00111 {
00112
00113 memory=new mempool( sizeof(entry<T>) , BlockSize );
00114
00115 table = new entry<T>* [ size=n ];
00116
00117 memset(table,0,sizeof(entry<T> *) * n );
00118
00119 set_keylen(kl);
00120
00121 keys = accesses = collisions = 0;
00122 }
00123
00124 template <class T>
00125 htable<T>::~htable()
00126 {
00127 delete []table;
00128 delete memory;
00129 }
00130
00131 template <class T>
00132 T htable<T>::find(T key)
00133 {
00134 address h;
00135 entry<T> *q,**p;
00136
00137 accesses++;
00138
00139 h = Hash(key);
00140
00141 p=&table[h%size];
00142 q=*p;
00143
00144
00145 while (q != NULL && Comp(q->key,key)) {
00146 p = &(q->next);
00147 q = q->next;
00148
00149 collisions++;
00150 }
00151
00152 if (q != NULL) return q->key;
00153
00154 return NULL;
00155 }
00156
00157 template <class T>
00158 T htable<T>::insert(T key)
00159 {
00160 address h;
00161 entry<T> *q,**p;
00162
00163 accesses++;
00164
00165 h = Hash(key);
00166
00167 p=&table[h%size];
00168 q=*p;
00169
00170
00171 while (q != NULL && Comp(q->key,key)) {
00172 p = &(q->next);
00173 q = q->next;
00174
00175 collisions++;
00176 }
00177
00178 if (q != NULL) return q->key;
00179
00180
00181 if ((q = (entry<T> *)memory->allocate()) == NULL)
00182 return NULL;
00183
00184
00185 *p = q;
00186
00187
00188 q->key = key;
00189 q->next = NULL;
00190 keys++;
00191
00192 return q->key;
00193 }
00194
00195 template <class T>
00196 T htable<T>::scan(HT_ACTION action)
00197 {
00198
00199 T k;
00200
00201 if (action == HT_INIT) {
00202 scan_i=0;
00203 scan_p=table[0];
00204 return NULL;
00205 }
00206
00207
00208 while ((scan_p==NULL) && (++scan_i<size)) scan_p=table[scan_i];
00209
00210 if (scan_p!=NULL) {
00211 k=scan_p->key;
00212 scan_p=(entry<T> *)scan_p->next;
00213 return k;
00214 };
00215
00216 return NULL;
00217 }
00218
00219
00220 template <class T>
00221 void htable<T>::map(ostream& co,int cols)
00222 {
00223
00224 entry<T> *p;
00225 char* img=new char[cols+1];
00226
00227 img[cols]='\0';
00228 memset(img,'.',cols);
00229
00230 co << "htable memory map: . (0 items), - (<5), # (>5)\n";
00231
00232 for (int i=0; i<size; i++) {
00233 int n=0;
00234 p=table[i];
00235
00236 while(p!=NULL) {
00237 n++;
00238 p=(entry<T> *)p->next;
00239 };
00240
00241 if (i && (i % cols)==0) {
00242 co << img << "\n";
00243 memset(img,'.',cols);
00244 }
00245
00246 if (n>0)
00247 img[i % cols]=n<=5?'-':'#';
00248
00249 }
00250
00251 img[size % cols]='\0';
00252 co << img << "\n";
00253
00254 delete []img;
00255 }
00256
00257 template <class T>
00258 void htable<T>::stat()
00259 {
00260 cerr << "htable class statistics\n";
00261 cerr << "size " << size
00262 << " keys " << keys
00263 << " acc " << accesses
00264 << " coll " << collisions
00265 << " used memory " << used()/1024 << "Kb\n";
00266 };
00267
00268
00269 #endif
00270
00271
00272