Kstars

SkipList.cpp
1 /*
2  File: SkipList.C
3  Author: Bruno Grossniklaus, 13.11.97
4  Mod: Gyorgy Fekete, Oct-09-2002
5  Version: 1.0
6  History:
7  Nov-13-1997; Gro; Version 1.0
8  Oct-09-2002; JHU; Version 1.1
9 
10 */
11 
12 #include <iostream> // cout
13 #include <iomanip> // setw
14 #include <cstdlib> // rand(), drand48()
15 
16 #include "SkipListElement.h"
17 #include "SkipList.h"
18 
19 #include <config-htmesh.h>
20 
21 #ifndef HAVE_DRAND48
22 double drand48()
23 {
24  double result;
25 #ifdef _WIN32
26  result = static_cast<double>(rand());
27  result /= RAND_MAX;
28 #else
29  result = static_cast<double>(random());
30  result /= LONG_MAX;
31 #endif
32  return result;
33 }
34 #endif /* HAVE_DRAND48 */
35 
36 ////////////////////////////////////////////////////////////////////////////////
37 // get new element level using given probability
38 ////////////////////////////////////////////////////////////////////////////////
39 long getNewLevel(long maxLevel, float probability)
40 {
41  long newLevel = 0;
42  while ((newLevel < maxLevel - 1) && (drand48() < probability)) // fast hack. fix later
43  newLevel++;
44  return (newLevel);
45 }
46 
47 ////////////////////////////////////////////////////////////////////////////////
48 SkipList::SkipList(float probability) : myProbability(probability)
49 {
50  myHeader = new SkipListElement(); // get memory for header element
51  myHeader->setKey(KEY_MAX);
52  myLength = 0;
53  iter = myHeader;
54 }
55 
56 ////////////////////////////////////////////////////////////////////////////////
57 SkipList::~SkipList()
58 {
59  delete myHeader; // free memory for header element
60 }
61 
62 ////////////////////////////////////////////////////////////////////////////////
63 void SkipList::insert(const Key searchKey, const Value value)
64 {
65  int i;
66  long newLevel;
67  SkipListElement *element;
68  SkipListElement *nextElement;
69  SkipListElement update(SKIPLIST_MAXLEVEL);
70 
71  // scan all levels while key < searchKey
72  // starting with header in his level
73  element = myHeader;
74  for (i = myHeader->getLevel(); i >= 0; i--)
75  {
76  nextElement = element->getElement(i);
77  while ((nextElement != NIL) && (nextElement->getKey() < searchKey))
78  {
79  element = nextElement;
80  nextElement = element->getElement(i);
81  }
82  // save level pointer
83  update.setElement(i, element);
84  }
85 
86  // key is < searchKey
87  element = element->getElement(0);
88 
89  if ((element != NIL) && (element->getKey() == searchKey))
90  {
91  // key exists. set new value
92  element->setValue(value);
93  }
94  else
95  {
96  // new key. add to list
97  // get new level and fix list level
98 
99  // get new level
100  newLevel = getNewLevel(SKIPLIST_MAXLEVEL, myProbability);
101  if (newLevel > myHeader->getLevel())
102  {
103  // adjust header level
104  for (i = myHeader->getLevel() + 1; i <= newLevel; i++)
105  {
106  // adjust new pointer of new element
107  update.setElement(i, myHeader);
108  }
109  // set new header level
110  myHeader->setLevel(newLevel);
111  }
112  // make new element [NEW *******]
113  myLength++;
114  element = new SkipListElement(newLevel, searchKey, value);
115  for (i = 0; i <= newLevel; i++) // scan all levels
116  {
117  // set next pointer of new element
118  element->setElement(i, update.getElement(i)->getElement(i));
119  update.getElement(i)->setElement(i, element);
120  }
121  }
122 }
123 
124 ////////////////////////////////////////////////////////////////////////////////
125 // greatest key less than searchKey.. almost completely, but not
126 // quite entirely unlike a search ...
127 Key SkipList::findMAX(const Key searchKey) const
128 {
129  int i;
130  SkipListElement *element;
131  SkipListElement *nextElement;
132  Key retKey;
133 
134  element = myHeader;
135  for (i = myHeader->getLevel(); i >= 0; i--)
136  {
137  nextElement = element->getElement(i);
138  while ((nextElement != NIL) && (nextElement->getKey() < searchKey))
139  {
140  element = nextElement;
141  nextElement = element->getElement(i);
142  }
143  }
144  // now nextElement is >= searhcKey
145  // and element is < searchKey
146  // therefore element key is largest key less than current
147 
148  // if this were search:
149  // element=element->getElement(0); // skip to >=
150  if (element != NIL)
151  {
152  retKey = element->getKey();
153  return retKey == KEY_MAX ? (-KEY_MAX) : retKey;
154  }
155  else
156  {
157  return ((Key)KEY_MAX);
158  }
159 }
160 
161 // smallest greater than searchKey.. almost completely, but not
162 // quite entirely unlike a search ...
163 Key SkipList::findMIN(const Key searchKey) const
164 {
165  int i;
166  SkipListElement *element(myHeader);
167  SkipListElement *nextElement = nullptr;
168  Key retKey;
169 
170  for (i = myHeader->getLevel(); i >= 0; i--)
171  {
172  nextElement = element->getElement(i);
173  while ((nextElement != NIL) && (nextElement->getKey() <= searchKey))
174  {
175  element = nextElement;
176  nextElement = element->getElement(i);
177  }
178  }
179  // now nextElement is > searchKey
180  // element is <= , make it >
181  //
182  element = nextElement;
183  if (element != NIL)
184  {
185  retKey = element->getKey();
186  return retKey == KEY_MAX ? (-KEY_MAX) : retKey;
187  }
188  else
189  {
190  return (Key)KEY_MAX;
191  }
192 }
193 
194 ////////////////////////////////////////////////////////////////////////////////
195 /* Very similar to free, but frees a range of keys
196  from lo to hi, inclusive */
197 void SkipList::freeRange(const Key loKey, const Key hiKey)
198 {
199  int i;
200  SkipListElement *element;
201  SkipListElement *nextElement;
202 
203  // scan all levels while key < searchKey
204  // starting with header in his level
205  element = myHeader;
206  for (i = myHeader->getLevel(); i >= 0; i--)
207  {
208  nextElement = element->getElement(i);
209  while ((nextElement != NIL) && (nextElement->getKey() < loKey))
210  {
211  element = nextElement;
212  nextElement = element->getElement(i);
213  }
214  }
215  // key is < loKey
216  element = element->getElement(0);
217 
218  while ((element != NIL) && (element->getKey() <= hiKey))
219  {
220  nextElement = element->getElement(0);
221  free(element->getKey());
222  element = nextElement;
223  }
224 }
225 
226 ////////////////////////////////////////////////////////////////////////////////
227 void SkipList::free(const Key searchKey)
228 {
229  int i;
230  SkipListElement *element;
231  SkipListElement *nextElement;
232  SkipListElement update(SKIPLIST_MAXLEVEL);
233 
234  // scan all levels while key < searchKey
235  // starting with header in his level
236  element = myHeader;
237  for (i = myHeader->getLevel(); i >= 0; i--)
238  {
239  nextElement = element->getElement(i);
240  while ((nextElement != NIL) && (nextElement->getKey() < searchKey))
241  {
242  element = nextElement;
243  nextElement = element->getElement(i);
244  }
245  // save level pointer
246  update.setElement(i, element);
247  }
248 
249  // key is < searchKey
250  element = element->getElement(0);
251 
252  // if key exists
253  if ((element != NIL) && (element->getKey() == searchKey))
254  {
255  for (i = 0; i <= myHeader->getLevel(); i++) // save next pointers
256  {
257  if (update.getElement(i)->getElement(i) == element)
258  {
259  update.getElement(i)->setElement(i, element->getElement(i));
260  }
261  }
262 
263  // free memory of element
264  delete element;
265  myLength--;
266 
267  // set new header level
268  while ((myHeader->getLevel() > 0) && (myHeader->getElement(myHeader->getLevel()) == NIL))
269  {
270  myHeader->setLevel(myHeader->getLevel() - 1);
271  }
272  }
273 }
274 
275 //// STATISTICS on skiplist
277 {
278  int count = 0;
279  SkipListElement *element;
280  SkipListElement *nextElement;
281 
282  element = myHeader;
283  nextElement = element->getElement(0);
284 
285  while ((nextElement != NIL))
286  {
287  count++;
288  element = nextElement;
289  nextElement = element->getElement(0);
290  }
291  std::cout << "Have number of elements ... " << count << std::endl;
292  std::cout << "Size ..................... " << myLength << std::endl;
293  {
294  int *hist;
295  hist = new int[20];
296  int i;
297  long totalPointers, usedPointers;
298  for (i = 0; i < 20; i++)
299  {
300  hist[i] = 0;
301  }
302  element = myHeader;
303  count = 0;
304  nextElement = element->getElement(0);
305  while ((nextElement != NIL))
306  {
307  count++;
308  hist[nextElement->getLevel()]++;
309  element = nextElement;
310  nextElement = element->getElement(0);
311  }
312  //
313  // There are SKIPLIST_MAXLEVEL * count available pointers
314  //
315  totalPointers = SKIPLIST_MAXLEVEL * count;
316  usedPointers = 0;
317  //
318  // of these every node that is not at the max level wastes some
319  //
320  for (i = 0; i < 20; i++)
321  {
322  if (hist[i] > 0)
323  std::cout << std::setw(2) << i << ": " << std::setw(6) << hist[i] << std::endl;
324  usedPointers += hist[i] * (1 + i);
325  }
326  std::cout << "Used pointers " << usedPointers << std::endl;
327  std::cout << "Total pointers " << totalPointers
328  << " efficiency = " << (double)usedPointers / (double)totalPointers << std::endl;
329  delete[] hist;
330  }
331  return;
332 }
KCOREADDONS_EXPORT int random()
void free(const Key searchKey)
free element with key
Definition: SkipList.cpp:227
void insert(const Key searchKey, const Value value)
insert new element
Definition: SkipList.cpp:63
void stat()
statistics;
Definition: SkipList.cpp:276
Key findMAX(const Key searchKey) const
search element with key NGT searchKey
Definition: SkipList.cpp:127
Key findMIN(const Key searchKey) const
search element with key NLT searchKey
Definition: SkipList.cpp:163
This file is part of the KDE documentation.
Documentation copyright © 1996-2022 The KDE developers.
Generated on Fri Aug 12 2022 04:00:58 by doxygen 1.8.17 written by Dimitri van Heesch, © 1997-2006

KDE's Doxygen guidelines are available online.