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