37 #ifndef RTPKEYHASHTABLE_H
39 #define RTPKEYHASHTABLE_H
41 #include "rtpconfig.h"
49 template<
class Key,
class Element,
class GetIndex,
int hashsize>
50 class RTPKeyHashTable :
public RTPMemoryObject
54 ~RTPKeyHashTable() { 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 Key &GetCurrentKey() {
return curhashelem->GetKey(); }
62 int GotoElement(
const Key &k);
63 bool HasElement(
const Key &k);
64 void GotoNextElement();
65 void GotoPreviousElement();
68 int AddElement(
const Key &k,
const Element &elem);
69 int DeleteElement(
const Key &k);
78 HashElement(
const Key &k,
const Element &e,
int index):key(k),element(e) { hashprev = 0; hashnext = 0; listnext = 0; listprev = 0; hashindex = index; }
79 int GetHashIndex() {
return hashindex; }
80 Key &GetKey() {
return key; }
81 Element &GetElement() {
return element; }
83 void Dump() { std::cout <<
"\tHash index " << hashindex <<
" | Key " << key <<
" | Element " << element << std::endl; }
90 HashElement *hashprev,*hashnext;
91 HashElement *listprev,*listnext;
94 HashElement *table[hashsize];
95 HashElement *firsthashelem,*lasthashelem;
96 HashElement *curhashelem;
97 #ifdef RTP_SUPPORT_MEMORYMANAGEMENT
99 #endif // RTP_SUPPORT_MEMORYMANAGEMENT
102 template<
class Key,
class Element,
class GetIndex,
int hashsize>
103 inline RTPKeyHashTable<Key,Element,GetIndex,hashsize>::RTPKeyHashTable(
RTPMemoryManager *mgr,
int memtype) : RTPMemoryObject(mgr)
105 for (
int i = 0 ; i < hashsize ; i++)
109 #ifdef RTP_SUPPORT_MEMORYMANAGEMENT
110 memorytype = memtype;
111 #endif // RTP_SUPPORT_MEMORYMANAGEMENT
114 template<
class Key,
class Element,
class GetIndex,
int hashsize>
115 inline int RTPKeyHashTable<Key,Element,GetIndex,hashsize>::DeleteCurrentElement()
119 HashElement *tmp1,*tmp2;
124 index = curhashelem->GetHashIndex();
125 tmp1 = curhashelem->hashprev;
126 tmp2 = curhashelem->hashnext;
135 tmp1->hashnext = tmp2;
137 tmp2->hashprev = tmp1;
142 tmp1 = curhashelem->listprev;
143 tmp2 = curhashelem->listnext;
146 firsthashelem = tmp2;
154 tmp1->listnext = tmp2;
156 tmp2->listprev = tmp1;
162 RTPDelete(curhashelem,GetMemoryManager());
166 return ERR_RTP_KEYHASHTABLE_NOCURRENTELEMENT;
170 template<
class Key,
class Element,
class GetIndex,
int hashsize>
171 inline int RTPKeyHashTable<Key,Element,GetIndex,hashsize>::GotoElement(
const Key &k)
176 index = GetIndex::GetIndex(k);
177 if (index >= hashsize)
178 return ERR_RTP_KEYHASHTABLE_FUNCTIONRETURNEDINVALIDHASHINDEX;
180 curhashelem = table[index];
182 while(!found && curhashelem != 0)
184 if (curhashelem->GetKey() == k)
187 curhashelem = curhashelem->hashnext;
190 return ERR_RTP_KEYHASHTABLE_KEYNOTFOUND;
194 template<
class Key,
class Element,
class GetIndex,
int hashsize>
195 inline bool RTPKeyHashTable<Key,Element,GetIndex,hashsize>::HasElement(
const Key &k)
201 index = GetIndex::GetIndex(k);
202 if (index >= hashsize)
207 while(!found && tmp != 0)
209 if (tmp->GetKey() == k)
217 template<
class Key,
class Element,
class GetIndex,
int hashsize>
218 inline void RTPKeyHashTable<Key,Element,GetIndex,hashsize>::GotoNextElement()
221 curhashelem = curhashelem->listnext;
224 template<
class Key,
class Element,
class GetIndex,
int hashsize>
225 inline void RTPKeyHashTable<Key,Element,GetIndex,hashsize>::GotoPreviousElement()
228 curhashelem = curhashelem->listprev;
231 template<
class Key,
class Element,
class GetIndex,
int hashsize>
232 inline void RTPKeyHashTable<Key,Element,GetIndex,hashsize>::Clear()
234 HashElement *tmp1,*tmp2;
236 for (
int i = 0 ; i < hashsize ; i++)
239 tmp1 = firsthashelem;
242 tmp2 = tmp1->listnext;
243 RTPDelete(tmp1,GetMemoryManager());
250 template<
class Key,
class Element,
class GetIndex,
int hashsize>
251 inline int RTPKeyHashTable<Key,Element,GetIndex,hashsize>::AddElement(
const Key &k,
const Element &elem)
255 HashElement *e,*newelem;
257 index = GetIndex::GetIndex(k);
258 if (index >= hashsize)
259 return ERR_RTP_KEYHASHTABLE_FUNCTIONRETURNEDINVALIDHASHINDEX;
263 while(!found && e != 0)
265 if (e->GetKey() == k)
271 return ERR_RTP_KEYHASHTABLE_KEYALREADYEXISTS;
275 newelem = RTPNew(GetMemoryManager(),memorytype) HashElement(k,elem,index);
277 return ERR_RTP_OUTOFMEM;
280 table[index] = newelem;
281 newelem->hashnext = e;
283 e->hashprev = newelem;
287 if (firsthashelem == 0)
289 firsthashelem = newelem;
290 lasthashelem = newelem;
294 lasthashelem->listnext = newelem;
295 newelem->listprev = lasthashelem;
296 lasthashelem = newelem;
301 template<
class Key,
class Element,
class GetIndex,
int hashsize>
302 inline int RTPKeyHashTable<Key,Element,GetIndex,hashsize>::DeleteElement(
const Key &k)
306 status = GotoElement(k);
309 return DeleteCurrentElement();
313 template<
class Key,
class Element,
class GetIndex,
int hashsize>
314 inline void RTPKeyHashTable<Key,Element,GetIndex,hashsize>::Dump()
318 std::cout <<
"DUMPING TABLE CONTENTS:" << std::endl;
319 for (
int i = 0 ; i < hashsize ; i++)
329 std::cout <<
"DUMPING LIST CONTENTS:" << std::endl;
339 #endif // RTPKEYHASHTABLE_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