SDRAngel  4.11.5
Developer docs for <a href="https://github.com/f4exb/sdrangel">SDRangel<\a>, an Open Source Qt5 / OpenGL 3.0+ SDR and signal analyzer frontend to various hardware.
rtpkeyhashtable.h
Go to the documentation of this file.
1 /*
2 
3  This file is a part of JRTPLIB
4  Copyright (c) 1999-2017 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 
37 #ifndef RTPKEYHASHTABLE_H
38 
39 #define RTPKEYHASHTABLE_H
40 
41 #include "rtpconfig.h"
42 #include "rtperrors.h"
43 
44 namespace qrtplib
45 {
46 
47 template<class Key, class Element, class GetIndex, int hashsize>
49 {
50 public:
53  {
54  Clear();
55  }
56 
58  {
60  }
62  {
64  }
66  {
67  return (curhashelem == 0) ? false : true;
68  }
70  Element &GetCurrentElement()
71  {
72  return curhashelem->GetElement();
73  }
75  {
76  return curhashelem->GetKey();
77  }
78  int GotoElement(const Key &k);
79  bool HasElement(const Key &k);
80  void GotoNextElement();
81  void GotoPreviousElement();
82  void Clear();
83 
84  int AddElement(const Key &k, const Element &elem);
85  int DeleteElement(const Key &k);
86 
87 private:
89  {
90  public:
91  HashElement(const Key &k, const Element &e, int index) :
92  key(k), element(e)
93  {
94  hashprev = 0;
95  hashnext = 0;
96  listnext = 0;
97  listprev = 0;
98  hashindex = index;
99  }
101  {
102  return hashindex;
103  }
104  Key &GetKey()
105  {
106  return key;
107  }
108  Element &GetElement()
109  {
110  return element;
111  }
112 
113  private:
115  Key key;
116  Element element;
117  public:
120  };
121 
122  HashElement *table[hashsize];
125 };
126 
127 template<class Key, class Element, class GetIndex, int hashsize>
129 {
130  for (int i = 0; i < hashsize; i++)
131  table[i] = 0;
132  firsthashelem = 0;
133  lasthashelem = 0;
134 }
135 
136 template<class Key, class Element, class GetIndex, int hashsize>
138 {
139  if (curhashelem)
140  {
141  HashElement *tmp1, *tmp2;
142  int index;
143 
144  // First, relink elements in current hash bucket
145 
146  index = curhashelem->GetHashIndex();
147  tmp1 = curhashelem->hashprev;
148  tmp2 = curhashelem->hashnext;
149  if (tmp1 == 0) // no previous element in hash bucket
150  {
151  table[index] = tmp2;
152  if (tmp2 != 0)
153  tmp2->hashprev = 0;
154  }
155  else // there is a previous element in the hash bucket
156  {
157  tmp1->hashnext = tmp2;
158  if (tmp2 != 0)
159  tmp2->hashprev = tmp1;
160  }
161 
162  // Relink elements in list
163 
164  tmp1 = curhashelem->listprev;
165  tmp2 = curhashelem->listnext;
166  if (tmp1 == 0) // curhashelem is first in list
167  {
168  firsthashelem = tmp2;
169  if (tmp2 != 0)
170  tmp2->listprev = 0;
171  else
172  // curhashelem is also last in list
173  lasthashelem = 0;
174  }
175  else
176  {
177  tmp1->listnext = tmp2;
178  if (tmp2 != 0)
179  tmp2->listprev = tmp1;
180  else
181  // curhashelem is last in list
182  lasthashelem = tmp1;
183  }
184 
185  // finally, with everything being relinked, we can delete curhashelem
186  delete curhashelem;
187  curhashelem = tmp2; // Set to next element in list
188  }
189  else
191  return 0;
192 }
193 
194 template<class Key, class Element, class GetIndex, int hashsize>
196 {
197  int index;
198  bool found;
199 
200  index = GetIndex::GetIndex(k);
201  if (index >= hashsize)
203 
204  curhashelem = table[index];
205  found = false;
206  while (!found && curhashelem != 0)
207  {
208  if (curhashelem->GetKey() == k)
209  found = true;
210  else
212  }
213  if (!found)
215  return 0;
216 }
217 
218 template<class Key, class Element, class GetIndex, int hashsize>
220 {
221  int index;
222  bool found;
223  HashElement *tmp;
224 
225  index = GetIndex::GetIndex(k);
226  if (index >= hashsize)
227  return false;
228 
229  tmp = table[index];
230  found = false;
231  while (!found && tmp != 0)
232  {
233  if (tmp->GetKey() == k)
234  found = true;
235  else
236  tmp = tmp->hashnext;
237  }
238  return found;
239 }
240 
241 template<class Key, class Element, class GetIndex, int hashsize>
243 {
244  if (curhashelem)
246 }
247 
248 template<class Key, class Element, class GetIndex, int hashsize>
250 {
251  if (curhashelem)
253 }
254 
255 template<class Key, class Element, class GetIndex, int hashsize>
257 {
258  HashElement *tmp1, *tmp2;
259 
260  for (int i = 0; i < hashsize; i++)
261  table[i] = 0;
262 
263  tmp1 = firsthashelem;
264  while (tmp1 != 0)
265  {
266  tmp2 = tmp1->listnext;
267  delete tmp1;
268  tmp1 = tmp2;
269  }
270  firsthashelem = 0;
271  lasthashelem = 0;
272 }
273 
274 template<class Key, class Element, class GetIndex, int hashsize>
275 inline int RTPKeyHashTable<Key, Element, GetIndex, hashsize>::AddElement(const Key &k, const Element &elem)
276 {
277  int index;
278  bool found;
279  HashElement *e, *newelem;
280 
281  index = GetIndex::GetIndex(k);
282  if (index >= hashsize)
284 
285  e = table[index];
286  found = false;
287  while (!found && e != 0)
288  {
289  if (e->GetKey() == k)
290  found = true;
291  else
292  e = e->hashnext;
293  }
294  if (found)
296 
297  // Okay, the key doesn't exist, so we can add the new element in the hash table
298 
299  newelem = new HashElement(k, elem, index);
300 
301  e = table[index];
302  table[index] = newelem;
303  newelem->hashnext = e;
304  if (e != 0)
305  e->hashprev = newelem;
306 
307  // Now, we still got to add it to the linked list
308 
309  if (firsthashelem == 0)
310  {
311  firsthashelem = newelem;
312  lasthashelem = newelem;
313  }
314  else // there already are some elements in the list
315  {
316  lasthashelem->listnext = newelem;
317  newelem->listprev = lasthashelem;
318  lasthashelem = newelem;
319  }
320  return 0;
321 }
322 
323 template<class Key, class Element, class GetIndex, int hashsize>
325 {
326  int status;
327 
328  status = GotoElement(k);
329  if (status < 0)
330  return status;
331  return DeleteCurrentElement();
332 }
333 
334 } // end namespace
335 
336 #endif // RTPKEYHASHTABLE_H
int AddElement(const Key &k, const Element &elem)
#define ERR_RTP_KEYHASHTABLE_KEYALREADYEXISTS
Definition: rtperrors.h:61
int DeleteElement(const Key &k)
int GotoElement(const Key &k)
bool HasElement(const Key &k)
HashElement(const Key &k, const Element &e, int index)
int32_t i
Definition: decimators.h:244
#define ERR_RTP_KEYHASHTABLE_FUNCTIONRETURNEDINVALIDHASHINDEX
Definition: rtperrors.h:60
HashElement * table[hashsize]
#define ERR_RTP_KEYHASHTABLE_KEYNOTFOUND
Definition: rtperrors.h:62
#define ERR_RTP_KEYHASHTABLE_NOCURRENTELEMENT
Definition: rtperrors.h:63