File indexing completed on 2024-03-24 15:17:07

0001 /*
0002     File: SkipList.C
0003     Author: Bruno Grossniklaus, 13.11.97
0004     Mod:    Gyorgy Fekete, Oct-09-2002
0005     Version: 1.0
0006     History:
0007     Nov-13-1997; Gro; Version 1.0
0008     Oct-09-2002; JHU; Version 1.1
0009 
0010 */
0011 
0012 #include <iostream> // cout
0013 #include <iomanip>  // setw
0014 #include <cstdlib>  // rand(), drand48()
0015 
0016 #include "SkipListElement.h"
0017 #include "SkipList.h"
0018 
0019 #include <config-htmesh.h>
0020 
0021 #ifndef HAVE_DRAND48
0022 double drand48()
0023 {
0024     double result;
0025 #ifdef _WIN32
0026     result = static_cast<double>(rand());
0027     result /= RAND_MAX;
0028 #else
0029     result = static_cast<double>(random());
0030     result /= LONG_MAX;
0031 #endif
0032     return result;
0033 }
0034 #endif /* HAVE_DRAND48 */
0035 
0036 ////////////////////////////////////////////////////////////////////////////////
0037 // get new element level using given probability
0038 ////////////////////////////////////////////////////////////////////////////////
0039 long getNewLevel(long maxLevel, float probability)
0040 {
0041     long newLevel = 0;
0042     while ((newLevel < maxLevel - 1) && (drand48() < probability)) // fast hack. fix later
0043         newLevel++;
0044     return (newLevel);
0045 }
0046 
0047 ////////////////////////////////////////////////////////////////////////////////
0048 SkipList::SkipList(float probability) : myProbability(probability)
0049 {
0050     myHeader = new SkipListElement(); // get memory for header element
0051     myHeader->setKey(KEY_MAX);
0052     myLength = 0;
0053     iter     = myHeader;
0054 }
0055 
0056 ////////////////////////////////////////////////////////////////////////////////
0057 SkipList::~SkipList()
0058 {
0059     delete myHeader; // free memory for header element
0060 }
0061 
0062 ////////////////////////////////////////////////////////////////////////////////
0063 void SkipList::insert(const Key searchKey, const Value value)
0064 {
0065     int i;
0066     long newLevel;
0067     SkipListElement *element;
0068     SkipListElement *nextElement;
0069     SkipListElement update(SKIPLIST_MAXLEVEL);
0070 
0071     // scan all levels while key < searchKey
0072     // starting with header in his level
0073     element = myHeader;
0074     for (i = myHeader->getLevel(); i >= 0; i--)
0075     {
0076         nextElement = element->getElement(i);
0077         while ((nextElement != NIL) && (nextElement->getKey() < searchKey))
0078         {
0079             element     = nextElement;
0080             nextElement = element->getElement(i);
0081         }
0082         // save level pointer
0083         update.setElement(i, element);
0084     }
0085 
0086     // key is < searchKey
0087     element = element->getElement(0);
0088 
0089     if ((element != NIL) && (element->getKey() == searchKey))
0090     {
0091         // key exists. set new value
0092         element->setValue(value);
0093     }
0094     else
0095     {
0096         // new key. add to list
0097         // get new level and fix list level
0098 
0099         // get new level
0100         newLevel = getNewLevel(SKIPLIST_MAXLEVEL, myProbability);
0101         if (newLevel > myHeader->getLevel())
0102         {
0103             // adjust header level
0104             for (i = myHeader->getLevel() + 1; i <= newLevel; i++)
0105             {
0106                 // adjust new pointer of new element
0107                 update.setElement(i, myHeader);
0108             }
0109             // set new header level
0110             myHeader->setLevel(newLevel);
0111         }
0112         // make new element [NEW *******]
0113         myLength++;
0114         element = new SkipListElement(newLevel, searchKey, value);
0115         for (i = 0; i <= newLevel; i++) // scan all levels
0116         {
0117             // set next pointer of new element
0118             element->setElement(i, update.getElement(i)->getElement(i));
0119             update.getElement(i)->setElement(i, element);
0120         }
0121     }
0122 }
0123 
0124 ////////////////////////////////////////////////////////////////////////////////
0125 // greatest key less than searchKey.. almost completely, but not
0126 // quite entirely unlike a search ...
0127 Key SkipList::findMAX(const Key searchKey) const
0128 {
0129     int i;
0130     SkipListElement *element;
0131     SkipListElement *nextElement;
0132     Key retKey;
0133 
0134     element = myHeader;
0135     for (i = myHeader->getLevel(); i >= 0; i--)
0136     {
0137         nextElement = element->getElement(i);
0138         while ((nextElement != NIL) && (nextElement->getKey() < searchKey))
0139         {
0140             element     = nextElement;
0141             nextElement = element->getElement(i);
0142         }
0143     }
0144     // now nextElement is >= searhcKey
0145     // and element is < searchKey
0146     // therefore element  key is largest key less than current
0147 
0148     // if this were search:
0149     // element=element->getElement(0); // skip to >=
0150     if (element != NIL)
0151     {
0152         retKey = element->getKey();
0153         return retKey == KEY_MAX ? (-KEY_MAX) : retKey;
0154     }
0155     else
0156     {
0157         return ((Key)KEY_MAX);
0158     }
0159 }
0160 
0161 // smallest greater than searchKey.. almost completely, but not
0162 // quite entirely unlike a search ...
0163 Key SkipList::findMIN(const Key searchKey) const
0164 {
0165     int i;
0166     SkipListElement *element(myHeader);
0167     SkipListElement *nextElement = nullptr;
0168     Key retKey;
0169 
0170     for (i = myHeader->getLevel(); i >= 0; i--)
0171     {
0172         nextElement = element->getElement(i);
0173         while ((nextElement != NIL) && (nextElement->getKey() <= searchKey))
0174         {
0175             element     = nextElement;
0176             nextElement = element->getElement(i);
0177         }
0178     }
0179     // now nextElement is > searchKey
0180     // element is <= , make it >
0181     //
0182     element = nextElement;
0183     if (element != NIL)
0184     {
0185         retKey = element->getKey();
0186         return retKey == KEY_MAX ? (-KEY_MAX) : retKey;
0187     }
0188     else
0189     {
0190         return (Key)KEY_MAX;
0191     }
0192 }
0193 
0194 ////////////////////////////////////////////////////////////////////////////////
0195 /* Very similar to free, but frees a range of keys
0196    from lo to hi, inclusive */
0197 void SkipList::freeRange(const Key loKey, const Key hiKey)
0198 {
0199     int i;
0200     SkipListElement *element;
0201     SkipListElement *nextElement;
0202 
0203     // scan all levels while key < searchKey
0204     // starting with header in his level
0205     element = myHeader;
0206     for (i = myHeader->getLevel(); i >= 0; i--)
0207     {
0208         nextElement = element->getElement(i);
0209         while ((nextElement != NIL) && (nextElement->getKey() < loKey))
0210         {
0211             element     = nextElement;
0212             nextElement = element->getElement(i);
0213         }
0214     }
0215     // key is < loKey
0216     element = element->getElement(0);
0217 
0218     while ((element != NIL) && (element->getKey() <= hiKey))
0219     {
0220         nextElement = element->getElement(0);
0221         free(element->getKey());
0222         element = nextElement;
0223     }
0224 }
0225 
0226 ////////////////////////////////////////////////////////////////////////////////
0227 void SkipList::free(const Key searchKey)
0228 {
0229     int i;
0230     SkipListElement *element;
0231     SkipListElement *nextElement;
0232     SkipListElement update(SKIPLIST_MAXLEVEL);
0233 
0234     // scan all levels while key < searchKey
0235     // starting with header in his level
0236     element = myHeader;
0237     for (i = myHeader->getLevel(); i >= 0; i--)
0238     {
0239         nextElement = element->getElement(i);
0240         while ((nextElement != NIL) && (nextElement->getKey() < searchKey))
0241         {
0242             element     = nextElement;
0243             nextElement = element->getElement(i);
0244         }
0245         // save level pointer
0246         update.setElement(i, element);
0247     }
0248 
0249     // key is < searchKey
0250     element = element->getElement(0);
0251 
0252     // if key exists
0253     if ((element != NIL) && (element->getKey() == searchKey))
0254     {
0255         for (i = 0; i <= myHeader->getLevel(); i++) // save next pointers
0256         {
0257             if (update.getElement(i)->getElement(i) == element)
0258             {
0259                 update.getElement(i)->setElement(i, element->getElement(i));
0260             }
0261         }
0262 
0263         // free memory of element
0264         delete element;
0265         myLength--;
0266 
0267         // set new header level
0268         while ((myHeader->getLevel() > 0) && (myHeader->getElement(myHeader->getLevel()) == NIL))
0269         {
0270             myHeader->setLevel(myHeader->getLevel() - 1);
0271         }
0272     }
0273 }
0274 
0275 //// STATISTICS on skiplist
0276 void SkipList::stat()
0277 {
0278     int count = 0;
0279     SkipListElement *element;
0280     SkipListElement *nextElement;
0281 
0282     element     = myHeader;
0283     nextElement = element->getElement(0);
0284 
0285     while ((nextElement != NIL))
0286     {
0287         count++;
0288         element     = nextElement;
0289         nextElement = element->getElement(0);
0290     }
0291     std::cout << "Have number of elements ... " << count << std::endl;
0292     std::cout << "Size  ..................... " << myLength << std::endl;
0293     {
0294         int *hist;
0295         hist = new int[20];
0296         int i;
0297         long totalPointers, usedPointers;
0298         for (i = 0; i < 20; i++)
0299         {
0300             hist[i] = 0;
0301         }
0302         element     = myHeader;
0303         count       = 0;
0304         nextElement = element->getElement(0);
0305         while ((nextElement != NIL))
0306         {
0307             count++;
0308             hist[nextElement->getLevel()]++;
0309             element     = nextElement;
0310             nextElement = element->getElement(0);
0311         }
0312         //
0313         // There are SKIPLIST_MAXLEVEL * count available pointers
0314         //
0315         totalPointers = SKIPLIST_MAXLEVEL * count;
0316         usedPointers  = 0;
0317         //
0318         // of these every node that is not at the max level wastes some
0319         //
0320         for (i = 0; i < 20; i++)
0321         {
0322             if (hist[i] > 0)
0323                 std::cout << std::setw(2) << i << ": " << std::setw(6) << hist[i] << std::endl;
0324             usedPointers += hist[i] * (1 + i);
0325         }
0326         std::cout << "Used  pointers " << usedPointers << std::endl;
0327         std::cout << "Total pointers " << totalPointers
0328                   << " efficiency = " << (double)usedPointers / (double)totalPointers << std::endl;
0329         delete[] hist;
0330     }
0331     return;
0332 }