33 #ifndef RTPHASHTABLE_H
35 #define RTPHASHTABLE_H
49 template<
class Element,
class GetIndex,
int hashsize>
50 class RTPHashTable :
public RTPMemoryObject
54 ~RTPHashTable() { Clear(); }
56 void GotoFirstElement() { curhashelem = firsthashelem; }
57 void GotoLastElement() { curhashelem = lasthashelem; }
58 bool HasCurrentElement() {
return (curhashelem == 0)?
false:
true; }
59 int DeleteCurrentElement();
60 Element &GetCurrentElement() {
return curhashelem->GetElement(); }
61 int GotoElement(
const Element &e);
62 bool HasElement(
const Element &e);
63 void GotoNextElement();
64 void GotoPreviousElement();
67 int AddElement(
const Element &elem);
68 int DeleteElement(
const Element &elem);
77 HashElement(
const Element &e,
int index):element(e) { hashprev = 0; hashnext = 0; listnext = 0; listprev = 0; hashindex = index; }
78 int GetHashIndex() {
return hashindex; }
79 Element &GetElement() {
return element; }
81 void Dump() { std::cout <<
"\tHash index " << hashindex <<
" | Element " << element << std::endl; }
87 HashElement *hashprev,*hashnext;
88 HashElement *listprev,*listnext;
91 HashElement *table[hashsize];
92 HashElement *firsthashelem,*lasthashelem;
93 HashElement *curhashelem;
94 #ifdef RTP_SUPPORT_MEMORYMANAGEMENT
96 #endif // RTP_SUPPORT_MEMORYMANAGEMENT
99 template<
class Element,
class GetIndex,
int hashsize>
100 inline RTPHashTable<Element,GetIndex,hashsize>::RTPHashTable(
RTPMemoryManager *mgr,
int memtype) : RTPMemoryObject(mgr)
102 for (
int i = 0 ; i < hashsize ; i++)
106 #ifdef RTP_SUPPORT_MEMORYMANAGEMENT
107 memorytype = memtype;
108 #endif // RTP_SUPPORT_MEMORYMANAGEMENT
111 template<
class Element,
class GetIndex,
int hashsize>
112 inline int RTPHashTable<Element,GetIndex,hashsize>::DeleteCurrentElement()
116 HashElement *tmp1,*tmp2;
121 index = curhashelem->GetHashIndex();
122 tmp1 = curhashelem->hashprev;
123 tmp2 = curhashelem->hashnext;
132 tmp1->hashnext = tmp2;
134 tmp2->hashprev = tmp1;
139 tmp1 = curhashelem->listprev;
140 tmp2 = curhashelem->listnext;
143 firsthashelem = tmp2;
151 tmp1->listnext = tmp2;
153 tmp2->listprev = tmp1;
159 RTPDelete(curhashelem,GetMemoryManager());
163 return ERR_RTP_HASHTABLE_NOCURRENTELEMENT;
167 template<
class Element,
class GetIndex,
int hashsize>
168 inline int RTPHashTable<Element,GetIndex,hashsize>::GotoElement(
const Element &e)
173 index = GetIndex::GetIndex(e);
174 if (index >= hashsize)
175 return ERR_RTP_HASHTABLE_FUNCTIONRETURNEDINVALIDHASHINDEX;
177 curhashelem = table[index];
179 while(!found && curhashelem != 0)
181 if (curhashelem->GetElement() == e)
184 curhashelem = curhashelem->hashnext;
187 return ERR_RTP_HASHTABLE_ELEMENTNOTFOUND;
191 template<
class Element,
class GetIndex,
int hashsize>
192 inline bool RTPHashTable<Element,GetIndex,hashsize>::HasElement(
const Element &e)
198 index = GetIndex::GetIndex(e);
199 if (index >= hashsize)
204 while(!found && tmp != 0)
206 if (tmp->GetElement() == e)
214 template<
class Element,
class GetIndex,
int hashsize>
215 inline void RTPHashTable<Element,GetIndex,hashsize>::GotoNextElement()
218 curhashelem = curhashelem->listnext;
221 template<
class Element,
class GetIndex,
int hashsize>
222 inline void RTPHashTable<Element,GetIndex,hashsize>::GotoPreviousElement()
225 curhashelem = curhashelem->listprev;
228 template<
class Element,
class GetIndex,
int hashsize>
229 inline void RTPHashTable<Element,GetIndex,hashsize>::Clear()
231 HashElement *tmp1,*tmp2;
233 for (
int i = 0 ; i < hashsize ; i++)
236 tmp1 = firsthashelem;
239 tmp2 = tmp1->listnext;
240 RTPDelete(tmp1,GetMemoryManager());
247 template<
class Element,
class GetIndex,
int hashsize>
248 inline int RTPHashTable<Element,GetIndex,hashsize>::AddElement(
const Element &elem)
252 HashElement *e,*newelem;
254 index = GetIndex::GetIndex(elem);
255 if (index >= hashsize)
256 return ERR_RTP_HASHTABLE_FUNCTIONRETURNEDINVALIDHASHINDEX;
260 while(!found && e != 0)
262 if (e->GetElement() == elem)
268 return ERR_RTP_HASHTABLE_ELEMENTALREADYEXISTS;
272 newelem = RTPNew(GetMemoryManager(),memorytype) HashElement(elem,index);
274 return ERR_RTP_OUTOFMEM;
277 table[index] = newelem;
278 newelem->hashnext = e;
280 e->hashprev = newelem;
284 if (firsthashelem == 0)
286 firsthashelem = newelem;
287 lasthashelem = newelem;
291 lasthashelem->listnext = newelem;
292 newelem->listprev = lasthashelem;
293 lasthashelem = newelem;
298 template<
class Element,
class GetIndex,
int hashsize>
299 inline int RTPHashTable<Element,GetIndex,hashsize>::DeleteElement(
const Element &elem)
303 status = GotoElement(elem);
306 return DeleteCurrentElement();
310 template<
class Element,
class GetIndex,
int hashsize>
311 inline void RTPHashTable<Element,GetIndex,hashsize>::Dump()
315 std::cout <<
"DUMPING TABLE CONTENTS:" << std::endl;
316 for (
int i = 0 ; i < hashsize ; i++)
326 std::cout <<
"DUMPING LIST CONTENTS:" << std::endl;
336 #endif // RTPHASHTABLE_H
A memory manager.
Definition: rtpmemorymanager.h:144
#define RTPMEM_TYPE_OTHER
Used to indicate a general kind of memory block.
Definition: rtpmemorymanager.h:45