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
22double 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////////////////////////////////////////////////////////////////////////////////
39long 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////////////////////////////////////////////////////////////////////////////////
48SkipList::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////////////////////////////////////////////////////////////////////////////////
57SkipList::~SkipList()
58{
59 delete myHeader; // free memory for header element
60}
61
62////////////////////////////////////////////////////////////////////////////////
63void 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 ...
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 ...
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 */
197void 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////////////////////////////////////////////////////////////////////////////////
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;
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}
Interface for skip list elements See William Pugh's paper: Skip Lists: A Probabilistic Alternative to...
void insert(const Key searchKey, const Value value)
insert new element
Definition SkipList.cpp:63
Key findMAX(const Key searchKey) const
search element with key NGT searchKey
Definition SkipList.cpp:127
void free(const Key searchKey)
free element with key
Definition SkipList.cpp:227
void stat()
statistics;
Definition SkipList.cpp:276
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-2024 The KDE developers.
Generated on Sun Feb 25 2024 18:45:34 by doxygen 1.10.0 written by Dimitri van Heesch, © 1997-2006

KDE's Doxygen guidelines are available online.