19#include <config-htmesh.h>
26 result =
static_cast<double>(rand());
29 result =
static_cast<double>(random());
39long getNewLevel(
long maxLevel,
float probability)
42 while ((newLevel < maxLevel - 1) && (drand48() < probability))
48SkipList::SkipList(
float probability) : myProbability(probability)
50 myHeader =
new SkipListElement();
51 myHeader->setKey(KEY_MAX);
67 SkipListElement *element;
68 SkipListElement *nextElement;
69 SkipListElement update(SKIPLIST_MAXLEVEL);
74 for (i = myHeader->getLevel(); i >= 0; i--)
76 nextElement = element->getElement(i);
77 while ((nextElement != NIL) && (nextElement->getKey() < searchKey))
79 element = nextElement;
80 nextElement = element->getElement(i);
83 update.setElement(i, element);
87 element = element->getElement(0);
89 if ((element != NIL) && (element->getKey() == searchKey))
92 element->setValue(value);
100 newLevel = getNewLevel(SKIPLIST_MAXLEVEL, myProbability);
101 if (newLevel > myHeader->getLevel())
104 for (i = myHeader->getLevel() + 1; i <= newLevel; i++)
107 update.setElement(i, myHeader);
110 myHeader->setLevel(newLevel);
114 element =
new SkipListElement(newLevel, searchKey, value);
115 for (i = 0; i <= newLevel; i++)
118 element->setElement(i, update.getElement(i)->getElement(i));
119 update.getElement(i)->setElement(i, element);
130 SkipListElement *element;
131 SkipListElement *nextElement;
135 for (i = myHeader->getLevel(); i >= 0; i--)
137 nextElement = element->getElement(i);
138 while ((nextElement != NIL) && (nextElement->getKey() < searchKey))
140 element = nextElement;
141 nextElement = element->getElement(i);
152 retKey = element->getKey();
153 return retKey == KEY_MAX ? (-KEY_MAX) : retKey;
157 return ((Key)KEY_MAX);
166 SkipListElement *element(myHeader);
167 SkipListElement *nextElement =
nullptr;
170 for (i = myHeader->getLevel(); i >= 0; i--)
172 nextElement = element->getElement(i);
173 while ((nextElement != NIL) && (nextElement->getKey() <= searchKey))
175 element = nextElement;
176 nextElement = element->getElement(i);
182 element = nextElement;
185 retKey = element->getKey();
186 return retKey == KEY_MAX ? (-KEY_MAX) : retKey;
197void SkipList::freeRange(
const Key loKey,
const Key hiKey)
200 SkipListElement *element;
201 SkipListElement *nextElement;
206 for (i = myHeader->getLevel(); i >= 0; i--)
208 nextElement = element->getElement(i);
209 while ((nextElement != NIL) && (nextElement->getKey() < loKey))
211 element = nextElement;
212 nextElement = element->getElement(i);
216 element = element->getElement(0);
218 while ((element != NIL) && (element->getKey() <= hiKey))
220 nextElement = element->getElement(0);
221 free(element->getKey());
222 element = nextElement;
230 SkipListElement *element;
231 SkipListElement *nextElement;
232 SkipListElement update(SKIPLIST_MAXLEVEL);
237 for (i = myHeader->getLevel(); i >= 0; i--)
239 nextElement = element->getElement(i);
240 while ((nextElement != NIL) && (nextElement->getKey() < searchKey))
242 element = nextElement;
243 nextElement = element->getElement(i);
246 update.setElement(i, element);
250 element = element->getElement(0);
253 if ((element != NIL) && (element->getKey() == searchKey))
255 for (i = 0; i <= myHeader->getLevel(); i++)
257 if (update.getElement(i)->getElement(i) == element)
259 update.getElement(i)->setElement(i, element->getElement(i));
268 while ((myHeader->getLevel() > 0) && (myHeader->getElement(myHeader->getLevel()) == NIL))
270 myHeader->setLevel(myHeader->getLevel() - 1);
279 SkipListElement *element;
280 SkipListElement *nextElement;
283 nextElement = element->getElement(0);
285 while ((nextElement != NIL))
288 element = nextElement;
289 nextElement = element->getElement(0);
291 std::cout <<
"Have number of elements ... " << count << std::endl;
292 std::cout <<
"Size ..................... " << myLength << std::endl;
297 long totalPointers, usedPointers;
298 for (i = 0; i < 20; i++)
304 nextElement = element->getElement(0);
305 while ((nextElement != NIL))
308 hist[nextElement->getLevel()]++;
309 element = nextElement;
310 nextElement = element->getElement(0);
315 totalPointers = SKIPLIST_MAXLEVEL * count;
320 for (i = 0; i < 20; i++)
323 std::cout << std::setw(2) << i <<
": " << std::setw(6) << hist[i] << std::endl;
324 usedPointers += hist[i] * (1 + i);
326 std::cout <<
"Used pointers " << usedPointers << std::endl;
327 std::cout <<
"Total pointers " << totalPointers
328 <<
" efficiency = " << (double)usedPointers / (
double)totalPointers << std::endl;
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
Key findMAX(const Key searchKey) const
search element with key NGT searchKey
void free(const Key searchKey)
free element with key
Key findMIN(const Key searchKey) const
search element with key NLT searchKey
This file is part of the KDE documentation.
Documentation copyright © 1996-2024 The KDE developers.
Generated on Sat Dec 21 2024 17:04:46 by
doxygen 1.12.0 written
by
Dimitri van Heesch, © 1997-2006
KDE's Doxygen guidelines are available online.