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
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 ////////////////////////////////////////////////////////////////////////////////
getNewLevel(long maxLevel,float probability)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 ////////////////////////////////////////////////////////////////////////////////
SkipList(float probability)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 ////////////////////////////////////////////////////////////////////////////////
~SkipList()57 SkipList::~SkipList()
58 {
59     delete myHeader; // free memory for header element
60 }
61 
62 ////////////////////////////////////////////////////////////////////////////////
insert(const Key searchKey,const Value value)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 ...
findMAX(const Key searchKey) const127 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 ...
findMIN(const Key searchKey) const163 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 */
freeRange(const Key loKey,const Key hiKey)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 ////////////////////////////////////////////////////////////////////////////////
free(const Key searchKey)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
stat()276 void SkipList::stat()
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 }
333