Kstars
19#include <config-htmesh.h>
26 result =
static_cast<double>(
rand());
29 result =
static_cast<double>(random());
50 myHeader =
new SkipListElement();
51 myHeader->setKey(KEY_MAX);
67 SkipListElement *element;
69 SkipListElement update(SKIPLIST_MAXLEVEL);
74 for (i = myHeader->getLevel(); i >= 0; 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);
118 element->setElement(i, update.getElement(i)->getElement(i));
119 update.getElement(i)->setElement(i, element);
130 SkipListElement *element;
135 for (i = myHeader->getLevel(); i >= 0; i--)
152 retKey = element->getKey();
157 return ((
Key)KEY_MAX);
166 SkipListElement *element(myHeader);
170 for (i = myHeader->getLevel(); i >= 0; i--)
185 retKey = element->getKey();
200 SkipListElement *element;
206 for (i = myHeader->getLevel(); i >= 0; i--)
216 element = element->getElement(0);
218 while ((element != NIL) && (element->getKey() <=
hiKey))
221 free(element->getKey());
230 SkipListElement *element;
232 SkipListElement update(SKIPLIST_MAXLEVEL);
237 for (i = myHeader->getLevel(); i >= 0; 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;
291 std::cout <<
"Have number of elements ... " << count << std::endl;
292 std::cout <<
"Size ..................... " << myLength << std::endl;
298 for (i = 0; i < 20; i++)
320 for (i = 0; i < 20; i++)
323 std::cout << std::setw(2) << i <<
": " << std::setw(6) <<
hist[i] << std::endl;
326 std::cout <<
"Used pointers " <<
usedPointers << 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 Tue Mar 26 2024 11:19:03 by
doxygen 1.10.0 written
by
Dimitri van Heesch, © 1997-2006
KDE's Doxygen guidelines are available online.