00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00037 #ifndef RTPKEYHASHTABLE_H
00038
00039 #define RTPKEYHASHTABLE_H
00040
00041 #include "rtpconfig.h"
00042 #include "rtperrors.h"
00043 #include "rtpmemoryobject.h"
00044
00045 #ifdef RTPDEBUG
00046 #include <iostream>
00047 #endif // RTPDEBUG
00048
00049 template<class Key,class Element,class GetIndex,int hashsize>
00050 class RTPKeyHashTable : public RTPMemoryObject
00051 {
00052 public:
00053 RTPKeyHashTable(RTPMemoryManager *mgr = 0,int memtype = RTPMEM_TYPE_OTHER);
00054 ~RTPKeyHashTable() { Clear(); }
00055
00056 void GotoFirstElement() { curhashelem = firsthashelem; }
00057 void GotoLastElement() { curhashelem = lasthashelem; }
00058 bool HasCurrentElement() { return (curhashelem == 0)?false:true; }
00059 int DeleteCurrentElement();
00060 Element &GetCurrentElement() { return curhashelem->GetElement(); }
00061 Key &GetCurrentKey() { return curhashelem->GetKey(); }
00062 int GotoElement(const Key &k);
00063 bool HasElement(const Key &k);
00064 void GotoNextElement();
00065 void GotoPreviousElement();
00066 void Clear();
00067
00068 int AddElement(const Key &k,const Element &elem);
00069 int DeleteElement(const Key &k);
00070
00071 #ifdef RTPDEBUG
00072 void Dump();
00073 #endif // RTPDEBUG
00074 private:
00075 class HashElement
00076 {
00077 public:
00078 HashElement(const Key &k,const Element &e,int index):key(k),element(e) { hashprev = 0; hashnext = 0; listnext = 0; listprev = 0; hashindex = index; }
00079 int GetHashIndex() { return hashindex; }
00080 Key &GetKey() { return key; }
00081 Element &GetElement() { return element; }
00082 #ifdef RTPDEBUG
00083 void Dump() { std::cout << "\tHash index " << hashindex << " | Key " << key << " | Element " << element << std::endl; }
00084 #endif // RTPDEBUG
00085 private:
00086 int hashindex;
00087 Key key;
00088 Element element;
00089 public:
00090 HashElement *hashprev,*hashnext;
00091 HashElement *listprev,*listnext;
00092 };
00093
00094 HashElement *table[hashsize];
00095 HashElement *firsthashelem,*lasthashelem;
00096 HashElement *curhashelem;
00097 #ifdef RTP_SUPPORT_MEMORYMANAGEMENT
00098 int memorytype;
00099 #endif // RTP_SUPPORT_MEMORYMANAGEMENT
00100 };
00101
00102 template<class Key,class Element,class GetIndex,int hashsize>
00103 inline RTPKeyHashTable<Key,Element,GetIndex,hashsize>::RTPKeyHashTable(RTPMemoryManager *mgr,int memtype) : RTPMemoryObject(mgr)
00104 {
00105 for (int i = 0 ; i < hashsize ; i++)
00106 table[i] = 0;
00107 firsthashelem = 0;
00108 lasthashelem = 0;
00109 #ifdef RTP_SUPPORT_MEMORYMANAGEMENT
00110 memorytype = memtype;
00111 #endif // RTP_SUPPORT_MEMORYMANAGEMENT
00112 }
00113
00114 template<class Key,class Element,class GetIndex,int hashsize>
00115 inline int RTPKeyHashTable<Key,Element,GetIndex,hashsize>::DeleteCurrentElement()
00116 {
00117 if (curhashelem)
00118 {
00119 HashElement *tmp1,*tmp2;
00120 int index;
00121
00122
00123
00124 index = curhashelem->GetHashIndex();
00125 tmp1 = curhashelem->hashprev;
00126 tmp2 = curhashelem->hashnext;
00127 if (tmp1 == 0)
00128 {
00129 table[index] = tmp2;
00130 if (tmp2 != 0)
00131 tmp2->hashprev = 0;
00132 }
00133 else
00134 {
00135 tmp1->hashnext = tmp2;
00136 if (tmp2 != 0)
00137 tmp2->hashprev = tmp1;
00138 }
00139
00140
00141
00142 tmp1 = curhashelem->listprev;
00143 tmp2 = curhashelem->listnext;
00144 if (tmp1 == 0)
00145 {
00146 firsthashelem = tmp2;
00147 if (tmp2 != 0)
00148 tmp2->listprev = 0;
00149 else
00150 lasthashelem = 0;
00151 }
00152 else
00153 {
00154 tmp1->listnext = tmp2;
00155 if (tmp2 != 0)
00156 tmp2->listprev = tmp1;
00157 else
00158 lasthashelem = tmp1;
00159 }
00160
00161
00162 RTPDelete(curhashelem,GetMemoryManager());
00163 curhashelem = tmp2;
00164 }
00165 else
00166 return ERR_RTP_KEYHASHTABLE_NOCURRENTELEMENT;
00167 return 0;
00168 }
00169
00170 template<class Key,class Element,class GetIndex,int hashsize>
00171 inline int RTPKeyHashTable<Key,Element,GetIndex,hashsize>::GotoElement(const Key &k)
00172 {
00173 int index;
00174 bool found;
00175
00176 index = GetIndex::GetIndex(k);
00177 if (index >= hashsize)
00178 return ERR_RTP_KEYHASHTABLE_FUNCTIONRETURNEDINVALIDHASHINDEX;
00179
00180 curhashelem = table[index];
00181 found = false;
00182 while(!found && curhashelem != 0)
00183 {
00184 if (curhashelem->GetKey() == k)
00185 found = true;
00186 else
00187 curhashelem = curhashelem->hashnext;
00188 }
00189 if (!found)
00190 return ERR_RTP_KEYHASHTABLE_KEYNOTFOUND;
00191 return 0;
00192 }
00193
00194 template<class Key,class Element,class GetIndex,int hashsize>
00195 inline bool RTPKeyHashTable<Key,Element,GetIndex,hashsize>::HasElement(const Key &k)
00196 {
00197 int index;
00198 bool found;
00199 HashElement *tmp;
00200
00201 index = GetIndex::GetIndex(k);
00202 if (index >= hashsize)
00203 return false;
00204
00205 tmp = table[index];
00206 found = false;
00207 while(!found && tmp != 0)
00208 {
00209 if (tmp->GetKey() == k)
00210 found = true;
00211 else
00212 tmp = tmp->hashnext;
00213 }
00214 return found;
00215 }
00216
00217 template<class Key,class Element,class GetIndex,int hashsize>
00218 inline void RTPKeyHashTable<Key,Element,GetIndex,hashsize>::GotoNextElement()
00219 {
00220 if (curhashelem)
00221 curhashelem = curhashelem->listnext;
00222 }
00223
00224 template<class Key,class Element,class GetIndex,int hashsize>
00225 inline void RTPKeyHashTable<Key,Element,GetIndex,hashsize>::GotoPreviousElement()
00226 {
00227 if (curhashelem)
00228 curhashelem = curhashelem->listprev;
00229 }
00230
00231 template<class Key,class Element,class GetIndex,int hashsize>
00232 inline void RTPKeyHashTable<Key,Element,GetIndex,hashsize>::Clear()
00233 {
00234 HashElement *tmp1,*tmp2;
00235
00236 for (int i = 0 ; i < hashsize ; i++)
00237 table[i] = 0;
00238
00239 tmp1 = firsthashelem;
00240 while (tmp1 != 0)
00241 {
00242 tmp2 = tmp1->listnext;
00243 RTPDelete(tmp1,GetMemoryManager());
00244 tmp1 = tmp2;
00245 }
00246 firsthashelem = 0;
00247 lasthashelem = 0;
00248 }
00249
00250 template<class Key,class Element,class GetIndex,int hashsize>
00251 inline int RTPKeyHashTable<Key,Element,GetIndex,hashsize>::AddElement(const Key &k,const Element &elem)
00252 {
00253 int index;
00254 bool found;
00255 HashElement *e,*newelem;
00256
00257 index = GetIndex::GetIndex(k);
00258 if (index >= hashsize)
00259 return ERR_RTP_KEYHASHTABLE_FUNCTIONRETURNEDINVALIDHASHINDEX;
00260
00261 e = table[index];
00262 found = false;
00263 while(!found && e != 0)
00264 {
00265 if (e->GetKey() == k)
00266 found = true;
00267 else
00268 e = e->hashnext;
00269 }
00270 if (found)
00271 return ERR_RTP_KEYHASHTABLE_KEYALREADYEXISTS;
00272
00273
00274
00275 newelem = RTPNew(GetMemoryManager(),memorytype) HashElement(k,elem,index);
00276 if (newelem == 0)
00277 return ERR_RTP_OUTOFMEM;
00278
00279 e = table[index];
00280 table[index] = newelem;
00281 newelem->hashnext = e;
00282 if (e != 0)
00283 e->hashprev = newelem;
00284
00285
00286
00287 if (firsthashelem == 0)
00288 {
00289 firsthashelem = newelem;
00290 lasthashelem = newelem;
00291 }
00292 else
00293 {
00294 lasthashelem->listnext = newelem;
00295 newelem->listprev = lasthashelem;
00296 lasthashelem = newelem;
00297 }
00298 return 0;
00299 }
00300
00301 template<class Key,class Element,class GetIndex,int hashsize>
00302 inline int RTPKeyHashTable<Key,Element,GetIndex,hashsize>::DeleteElement(const Key &k)
00303 {
00304 int status;
00305
00306 status = GotoElement(k);
00307 if (status < 0)
00308 return status;
00309 return DeleteCurrentElement();
00310 }
00311
00312 #ifdef RTPDEBUG
00313 template<class Key,class Element,class GetIndex,int hashsize>
00314 inline void RTPKeyHashTable<Key,Element,GetIndex,hashsize>::Dump()
00315 {
00316 HashElement *e;
00317
00318 std::cout << "DUMPING TABLE CONTENTS:" << std::endl;
00319 for (int i = 0 ; i < hashsize ; i++)
00320 {
00321 e = table[i];
00322 while (e != 0)
00323 {
00324 e->Dump();
00325 e = e->hashnext;
00326 }
00327 }
00328
00329 std::cout << "DUMPING LIST CONTENTS:" << std::endl;
00330 e = firsthashelem;
00331 while (e != 0)
00332 {
00333 e->Dump();
00334 e = e->listnext;
00335 }
00336 }
00337 #endif // RTPDEBUG
00338
00339 #endif // RTPKEYHASHTABLE_H