JRTPLIB  3.10.0
rtphashtable.h
Go to the documentation of this file.
1 /*
2 
3  This file is a part of JRTPLIB
4  Copyright (c) 1999-2016 Jori Liesenborgs
5 
6  Contact: jori.liesenborgs@gmail.com
7 
8  This library was developed at the Expertise Centre for Digital Media
9  (http://www.edm.uhasselt.be), a research center of the Hasselt University
10  (http://www.uhasselt.be). The library is based upon work done for
11  my thesis at the School for Knowledge Technology (Belgium/The Netherlands).
12 
13  Permission is hereby granted, free of charge, to any person obtaining a
14  copy of this software and associated documentation files (the "Software"),
15  to deal in the Software without restriction, including without limitation
16  the rights to use, copy, modify, merge, publish, distribute, sublicense,
17  and/or sell copies of the Software, and to permit persons to whom the
18  Software is furnished to do so, subject to the following conditions:
19 
20  The above copyright notice and this permission notice shall be included
21  in all copies or substantial portions of the Software.
22 
23  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
24  OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
25  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
26  THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
27  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
28  FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
29  IN THE SOFTWARE.
30 
31 */
32 
33 #ifndef RTPHASHTABLE_H
34 
35 #define RTPHASHTABLE_H
36 
41 #include "rtperrors.h"
42 #include "rtpmemoryobject.h"
43 
44 #ifdef RTPDEBUG
45 #include <iostream>
46 #endif // RTPDEBUG
47 
48 namespace jrtplib
49 {
50 
51 //template<class Element,int GetIndex(const Element &k),int hashsize>
52 template<class Element,class GetIndex,int hashsize>
53 class RTPHashTable : public RTPMemoryObject
54 {
55 public:
56  RTPHashTable(RTPMemoryManager *mgr = 0, int memtype = RTPMEM_TYPE_OTHER);
57  ~RTPHashTable() { Clear(); }
58 
59  void GotoFirstElement() { curhashelem = firsthashelem; }
60  void GotoLastElement() { curhashelem = lasthashelem; }
61  bool HasCurrentElement() { return (curhashelem == 0)?false:true; }
62  int DeleteCurrentElement();
63  Element &GetCurrentElement() { return curhashelem->GetElement(); }
64  int GotoElement(const Element &e);
65  bool HasElement(const Element &e);
66  void GotoNextElement();
67  void GotoPreviousElement();
68  void Clear();
69 
70  int AddElement(const Element &elem);
71  int DeleteElement(const Element &elem);
72 
73 #ifdef RTPDEBUG
74  void Dump();
75 #endif // RTPDEBUG
76 private:
77  class HashElement
78  {
79  public:
80  HashElement(const Element &e,int index):element(e) { hashprev = 0; hashnext = 0; listnext = 0; listprev = 0; hashindex = index; }
81  int GetHashIndex() { return hashindex; }
82  Element &GetElement() { return element; }
83 #ifdef RTPDEBUG
84  void Dump() { std::cout << "\tHash index " << hashindex << " | Element " << element << std::endl; }
85 #endif // RTPDEBUG
86  private:
87  int hashindex;
88  Element element;
89  public:
90  HashElement *hashprev,*hashnext;
91  HashElement *listprev,*listnext;
92  };
93 
94  HashElement *table[hashsize];
95  HashElement *firsthashelem,*lasthashelem;
96  HashElement *curhashelem;
97 #ifdef RTP_SUPPORT_MEMORYMANAGEMENT
98  int memorytype;
99 #endif // RTP_SUPPORT_MEMORYMANAGEMENT
100 };
101 
102 template<class Element,class GetIndex,int hashsize>
103 inline RTPHashTable<Element,GetIndex,hashsize>::RTPHashTable(RTPMemoryManager *mgr,int memtype) : RTPMemoryObject(mgr)
104 {
105  for (int i = 0 ; i < hashsize ; i++)
106  table[i] = 0;
107  firsthashelem = 0;
108  lasthashelem = 0;
109 #ifdef RTP_SUPPORT_MEMORYMANAGEMENT
110  memorytype = memtype;
111 #endif // RTP_SUPPORT_MEMORYMANAGEMENT
112 }
113 
114 template<class Element,class GetIndex,int hashsize>
115 inline int RTPHashTable<Element,GetIndex,hashsize>::DeleteCurrentElement()
116 {
117  if (curhashelem)
118  {
119  HashElement *tmp1,*tmp2;
120  int index;
121 
122  // First, relink elements in current hash bucket
123 
124  index = curhashelem->GetHashIndex();
125  tmp1 = curhashelem->hashprev;
126  tmp2 = curhashelem->hashnext;
127  if (tmp1 == 0) // no previous element in hash bucket
128  {
129  table[index] = tmp2;
130  if (tmp2 != 0)
131  tmp2->hashprev = 0;
132  }
133  else // there is a previous element in the hash bucket
134  {
135  tmp1->hashnext = tmp2;
136  if (tmp2 != 0)
137  tmp2->hashprev = tmp1;
138  }
139 
140  // Relink elements in list
141 
142  tmp1 = curhashelem->listprev;
143  tmp2 = curhashelem->listnext;
144  if (tmp1 == 0) // curhashelem is first in list
145  {
146  firsthashelem = tmp2;
147  if (tmp2 != 0)
148  tmp2->listprev = 0;
149  else // curhashelem is also last in list
150  lasthashelem = 0;
151  }
152  else
153  {
154  tmp1->listnext = tmp2;
155  if (tmp2 != 0)
156  tmp2->listprev = tmp1;
157  else // curhashelem is last in list
158  lasthashelem = tmp1;
159  }
160 
161  // finally, with everything being relinked, we can delete curhashelem
162  RTPDelete(curhashelem,GetMemoryManager());
163  curhashelem = tmp2; // Set to next element in the list
164  }
165  else
166  return ERR_RTP_HASHTABLE_NOCURRENTELEMENT;
167  return 0;
168 }
169 
170 template<class Element,class GetIndex,int hashsize>
171 inline int RTPHashTable<Element,GetIndex,hashsize>::GotoElement(const Element &e)
172 {
173  int index;
174  bool found;
175 
176  index = GetIndex::GetIndex(e);
177  if (index >= hashsize)
178  return ERR_RTP_HASHTABLE_FUNCTIONRETURNEDINVALIDHASHINDEX;
179 
180  curhashelem = table[index];
181  found = false;
182  while(!found && curhashelem != 0)
183  {
184  if (curhashelem->GetElement() == e)
185  found = true;
186  else
187  curhashelem = curhashelem->hashnext;
188  }
189  if (!found)
190  return ERR_RTP_HASHTABLE_ELEMENTNOTFOUND;
191  return 0;
192 }
193 
194 template<class Element,class GetIndex,int hashsize>
195 inline bool RTPHashTable<Element,GetIndex,hashsize>::HasElement(const Element &e)
196 {
197  int index;
198  bool found;
199  HashElement *tmp;
200 
201  index = GetIndex::GetIndex(e);
202  if (index >= hashsize)
203  return false;
204 
205  tmp = table[index];
206  found = false;
207  while(!found && tmp != 0)
208  {
209  if (tmp->GetElement() == e)
210  found = true;
211  else
212  tmp = tmp->hashnext;
213  }
214  return found;
215 }
216 
217 template<class Element,class GetIndex,int hashsize>
218 inline void RTPHashTable<Element,GetIndex,hashsize>::GotoNextElement()
219 {
220  if (curhashelem)
221  curhashelem = curhashelem->listnext;
222 }
223 
224 template<class Element,class GetIndex,int hashsize>
225 inline void RTPHashTable<Element,GetIndex,hashsize>::GotoPreviousElement()
226 {
227  if (curhashelem)
228  curhashelem = curhashelem->listprev;
229 }
230 
231 template<class Element,class GetIndex,int hashsize>
232 inline void RTPHashTable<Element,GetIndex,hashsize>::Clear()
233 {
234  HashElement *tmp1,*tmp2;
235 
236  for (int i = 0 ; i < hashsize ; i++)
237  table[i] = 0;
238 
239  tmp1 = firsthashelem;
240  while (tmp1 != 0)
241  {
242  tmp2 = tmp1->listnext;
243  RTPDelete(tmp1,GetMemoryManager());
244  tmp1 = tmp2;
245  }
246  firsthashelem = 0;
247  lasthashelem = 0;
248 }
249 
250 template<class Element,class GetIndex,int hashsize>
251 inline int RTPHashTable<Element,GetIndex,hashsize>::AddElement(const Element &elem)
252 {
253  int index;
254  bool found;
255  HashElement *e,*newelem;
256 
257  index = GetIndex::GetIndex(elem);
258  if (index >= hashsize)
259  return ERR_RTP_HASHTABLE_FUNCTIONRETURNEDINVALIDHASHINDEX;
260 
261  e = table[index];
262  found = false;
263  while(!found && e != 0)
264  {
265  if (e->GetElement() == elem)
266  found = true;
267  else
268  e = e->hashnext;
269  }
270  if (found)
271  return ERR_RTP_HASHTABLE_ELEMENTALREADYEXISTS;
272 
273  // Okay, the key doesn't exist, so we can add the new element in the hash table
274 
275  newelem = RTPNew(GetMemoryManager(),memorytype) HashElement(elem,index);
276  if (newelem == 0)
277  return ERR_RTP_OUTOFMEM;
278 
279  e = table[index];
280  table[index] = newelem;
281  newelem->hashnext = e;
282  if (e != 0)
283  e->hashprev = newelem;
284 
285  // Now, we still got to add it to the linked list
286 
287  if (firsthashelem == 0)
288  {
289  firsthashelem = newelem;
290  lasthashelem = newelem;
291  }
292  else // there already are some elements in the list
293  {
294  lasthashelem->listnext = newelem;
295  newelem->listprev = lasthashelem;
296  lasthashelem = newelem;
297  }
298  return 0;
299 }
300 
301 template<class Element,class GetIndex,int hashsize>
302 inline int RTPHashTable<Element,GetIndex,hashsize>::DeleteElement(const Element &elem)
303 {
304  int status;
305 
306  status = GotoElement(elem);
307  if (status < 0)
308  return status;
309  return DeleteCurrentElement();
310 }
311 
312 #ifdef RTPDEBUG
313 template<class Element,class GetIndex,int hashsize>
314 inline void RTPHashTable<Element,GetIndex,hashsize>::Dump()
315 {
316  HashElement *e;
317 
318  std::cout << "DUMPING TABLE CONTENTS:" << std::endl;
319  for (int i = 0 ; i < hashsize ; i++)
320  {
321  e = table[i];
322  while (e != 0)
323  {
324  e->Dump();
325  e = e->hashnext;
326  }
327  }
328 
329  std::cout << "DUMPING LIST CONTENTS:" << std::endl;
330  e = firsthashelem;
331  while (e != 0)
332  {
333  e->Dump();
334  e = e->listnext;
335  }
336 }
337 #endif // RTPDEBUG
338 
339 } // end namespace
340 
341 #endif // RTPHASHTABLE_H
342 
#define RTPMEM_TYPE_OTHER
Used to indicate a general kind of memory block.
Definition: rtpmemorymanager.h:45