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 }