00001
00032 #ifndef LL_LLPTRSKIPLIST_H
00033 #define LL_LLPTRSKIPLIST_H
00034
00035 #include "llerror.h"
00036
00037 #include "llrand.h"
00038
00040
00041
00042
00043
00044 template <class DATA_TYPE, S32 BINARY_DEPTH = 8>
00045 class LLPtrSkipList
00046 {
00047 public:
00048 friend class LLPtrSkipNode;
00049
00050
00051 LLPtrSkipList();
00052
00053 LLPtrSkipList(BOOL (*insert_first)(DATA_TYPE *first, DATA_TYPE *second),
00054 BOOL (*equals)(DATA_TYPE *first, DATA_TYPE *second));
00055 ~LLPtrSkipList();
00056
00057 inline void setInsertFirst(BOOL (*insert_first)(const DATA_TYPE *first, const DATA_TYPE *second));
00058 inline void setEquals(BOOL (*equals)(const DATA_TYPE *first, const DATA_TYPE *second));
00059
00060 inline BOOL addData(DATA_TYPE *data);
00061
00062 inline BOOL checkData(const DATA_TYPE *data);
00063
00064 inline S32 getLength();
00065
00066 inline BOOL removeData(const DATA_TYPE *data);
00067
00068
00069 inline BOOL moveData(const DATA_TYPE *data, LLPtrSkipList *newlist, BOOL b_sort);
00070
00071 inline BOOL moveCurrentData(LLPtrSkipList *newlist, BOOL b_sort);
00072
00073
00074
00075
00076
00077
00078
00079
00080
00081 inline void removeAllNodes();
00082
00083 inline BOOL deleteData(const DATA_TYPE *data);
00084
00085
00086 inline void deleteAllData();
00087
00088
00089 inline void resetList();
00090
00091
00092 inline DATA_TYPE *getCurrentData();
00093
00094
00095 inline DATA_TYPE *getNextData();
00096
00097
00098
00099 inline void removeCurrentData();
00100
00101
00102
00103 inline void deleteCurrentData();
00104
00105
00106 inline DATA_TYPE *getFirstData();
00107
00108
00109 inline BOOL corrupt();
00110
00111 protected:
00112 class LLPtrSkipNode
00113 {
00114 public:
00115 LLPtrSkipNode()
00116 : mData(NULL)
00117 {
00118 S32 i;
00119 for (i = 0; i < BINARY_DEPTH; i++)
00120 {
00121 mForward[i] = NULL;
00122 }
00123 }
00124
00125 LLPtrSkipNode(DATA_TYPE *data)
00126 : mData(data)
00127 {
00128 S32 i;
00129 for (i = 0; i < BINARY_DEPTH; i++)
00130 {
00131 mForward[i] = NULL;
00132 }
00133 }
00134
00135 ~LLPtrSkipNode()
00136 {
00137 if (mData)
00138 {
00139 llerror("Attempting to call LLPtrSkipNode destructor with a non-null mDatap!", 1);
00140 }
00141 }
00142
00143
00144 void deleteData()
00145 {
00146 delete mData;
00147 mData = NULL;
00148 }
00149
00150
00151 void removeData()
00152 {
00153 mData = NULL;
00154 }
00155
00156 DATA_TYPE *mData;
00157 LLPtrSkipNode *mForward[BINARY_DEPTH];
00158 };
00159
00160 static BOOL defaultEquals(const DATA_TYPE *first, const DATA_TYPE *second)
00161 {
00162 return first == second;
00163 }
00164
00165
00166 LLPtrSkipNode mHead;
00167 LLPtrSkipNode *mUpdate[BINARY_DEPTH];
00168 LLPtrSkipNode *mCurrentp;
00169 LLPtrSkipNode *mCurrentOperatingp;
00170 S32 mLevel;
00171 BOOL (*mInsertFirst)(const DATA_TYPE *first, const DATA_TYPE *second);
00172 BOOL (*mEquals)(const DATA_TYPE *first, const DATA_TYPE *second);
00173 };
00174
00175
00176
00177 template <class DATA_TYPE, S32 BINARY_DEPTH>
00178 LLPtrSkipList<DATA_TYPE, BINARY_DEPTH>::LLPtrSkipList()
00179 : mInsertFirst(NULL), mEquals(defaultEquals)
00180 {
00181 if (BINARY_DEPTH < 2)
00182 {
00183 llerrs << "Trying to create skip list with too little depth, "
00184 "must be 2 or greater" << llendl;
00185 }
00186 S32 i;
00187 for (i = 0; i < BINARY_DEPTH; i++)
00188 {
00189 mUpdate[i] = NULL;
00190 }
00191 mLevel = 1;
00192 mCurrentp = *(mHead.mForward);
00193 mCurrentOperatingp = *(mHead.mForward);
00194 }
00195
00196
00197 template <class DATA_TYPE, S32 BINARY_DEPTH>
00198 LLPtrSkipList<DATA_TYPE, BINARY_DEPTH>::LLPtrSkipList(BOOL (*insert_first)(DATA_TYPE *first, DATA_TYPE *second),
00199 BOOL (*equals)(DATA_TYPE *first, DATA_TYPE *second))
00200 :mInsertFirst(insert_first), mEquals(equals)
00201 {
00202 if (BINARY_DEPTH < 2)
00203 {
00204 llerrs << "Trying to create skip list with too little depth, "
00205 "must be 2 or greater" << llendl;
00206 }
00207 mLevel = 1;
00208 S32 i;
00209 for (i = 0; i < BINARY_DEPTH; i++)
00210 {
00211 mHead.mForward[i] = NULL;
00212 mUpdate[i] = NULL;
00213 }
00214 mCurrentp = *(mHead.mForward);
00215 mCurrentOperatingp = *(mHead.mForward);
00216 }
00217
00218 template <class DATA_TYPE, S32 BINARY_DEPTH>
00219 inline LLPtrSkipList<DATA_TYPE, BINARY_DEPTH>::~LLPtrSkipList()
00220 {
00221 removeAllNodes();
00222 }
00223
00224 template <class DATA_TYPE, S32 BINARY_DEPTH>
00225 inline void LLPtrSkipList<DATA_TYPE, BINARY_DEPTH>::setInsertFirst(BOOL (*insert_first)(const DATA_TYPE *first, const DATA_TYPE *second))
00226 {
00227 mInsertFirst = insert_first;
00228 }
00229
00230 template <class DATA_TYPE, S32 BINARY_DEPTH>
00231 inline void LLPtrSkipList<DATA_TYPE, BINARY_DEPTH>::setEquals(BOOL (*equals)(const DATA_TYPE *first, const DATA_TYPE *second))
00232 {
00233 mEquals = equals;
00234 }
00235
00236 template <class DATA_TYPE, S32 BINARY_DEPTH>
00237 inline BOOL LLPtrSkipList<DATA_TYPE, BINARY_DEPTH>::addData(DATA_TYPE *data)
00238 {
00239 S32 level;
00240 LLPtrSkipNode *current = &mHead;
00241 LLPtrSkipNode *temp;
00242
00243
00244 if (mInsertFirst)
00245 {
00246 for (level = mLevel - 1; level >= 0; level--)
00247 {
00248 temp = *(current->mForward + level);
00249 while ( (temp)
00250 &&(mInsertFirst(temp->mData, data)))
00251 {
00252 current = temp;
00253 temp = *(current->mForward + level);
00254 }
00255 *(mUpdate + level) = current;
00256 }
00257 }
00258 else
00259 {
00260 for (level = mLevel - 1; level >= 0; level--)
00261 {
00262 temp = *(current->mForward + level);
00263 while ( (temp)
00264 &&(temp->mData < data))
00265 {
00266 current = temp;
00267 temp = *(current->mForward + level);
00268 }
00269 *(mUpdate + level) = current;
00270 }
00271 }
00272
00273
00274
00275 current = *current->mForward;
00276
00277
00278 S32 newlevel;
00279 for (newlevel = 1; newlevel <= mLevel && newlevel < BINARY_DEPTH; newlevel++)
00280 {
00281 if (ll_frand() < 0.5f)
00282 break;
00283 }
00284
00285 LLPtrSkipNode *snode = new LLPtrSkipNode(data);
00286
00287 if (newlevel > mLevel)
00288 {
00289 mHead.mForward[mLevel] = NULL;
00290 mUpdate[mLevel] = &mHead;
00291 mLevel = newlevel;
00292 }
00293
00294 for (level = 0; level < newlevel; level++)
00295 {
00296 snode->mForward[level] = mUpdate[level]->mForward[level];
00297 mUpdate[level]->mForward[level] = snode;
00298 }
00299 return TRUE;
00300 }
00301
00302 template <class DATA_TYPE, S32 BINARY_DEPTH>
00303 inline BOOL LLPtrSkipList<DATA_TYPE, BINARY_DEPTH>::checkData(const DATA_TYPE *data)
00304 {
00305 S32 level;
00306 LLPtrSkipNode *current = &mHead;
00307 LLPtrSkipNode *temp;
00308
00309
00310 if (mInsertFirst)
00311 {
00312 for (level = mLevel - 1; level >= 0; level--)
00313 {
00314 temp = *(current->mForward + level);
00315 while ( (temp)
00316 &&(mInsertFirst(temp->mData, data)))
00317 {
00318 current = temp;
00319 temp = *(current->mForward + level);
00320 }
00321 *(mUpdate + level) = current;
00322 }
00323 }
00324 else
00325 {
00326 for (level = mLevel - 1; level >= 0; level--)
00327 {
00328 temp = *(current->mForward + level);
00329 while ( (temp)
00330 &&(temp->mData < data))
00331 {
00332 current = temp;
00333 temp = *(current->mForward + level);
00334 }
00335 *(mUpdate + level) = current;
00336 }
00337 }
00338
00339
00340
00341 current = *current->mForward;
00342
00343 if (current)
00344 {
00345 return mEquals(current->mData, data);
00346 }
00347 else
00348 {
00349 return FALSE;
00350 }
00351 }
00352
00353
00354 template <class DATA_TYPE, S32 BINARY_DEPTH>
00355 inline S32 LLPtrSkipList<DATA_TYPE, BINARY_DEPTH>::getLength()
00356 {
00357 U32 length = 0;
00358 for (LLPtrSkipNode* temp = *(mHead.mForward); temp != NULL; temp = temp->mForward[0])
00359 {
00360 length++;
00361 }
00362 return length;
00363 }
00364
00365 template <class DATA_TYPE, S32 BINARY_DEPTH>
00366 inline BOOL LLPtrSkipList<DATA_TYPE, BINARY_DEPTH>::removeData(const DATA_TYPE *data)
00367 {
00368 S32 level;
00369 LLPtrSkipNode *current = &mHead;
00370 LLPtrSkipNode *temp;
00371
00372
00373 if (mInsertFirst)
00374 {
00375 for (level = mLevel - 1; level >= 0; level--)
00376 {
00377 temp = *(current->mForward + level);
00378 while ( (temp)
00379 &&(mInsertFirst(temp->mData, data)))
00380 {
00381 current = temp;
00382 temp = *(current->mForward + level);
00383 }
00384 *(mUpdate + level) = current;
00385 }
00386 }
00387 else
00388 {
00389 for (level = mLevel - 1; level >= 0; level--)
00390 {
00391 temp = *(current->mForward + level);
00392 while ( (temp)
00393 &&(temp->mData < data))
00394 {
00395 current = temp;
00396 temp = *(current->mForward + level);
00397 }
00398 *(mUpdate + level) = current;
00399 }
00400 }
00401
00402
00403
00404 current = *current->mForward;
00405
00406 if (!current)
00407 {
00408
00409 return FALSE;
00410 }
00411
00412
00413 if (!mEquals(current->mData, data))
00414 {
00415
00416 return FALSE;
00417 }
00418 else
00419 {
00420
00421 for (level = 0; level < mLevel; level++)
00422 {
00423 if (mUpdate[level]->mForward[level] != current)
00424 {
00425
00426 break;
00427 }
00428 mUpdate[level]->mForward[level] = current->mForward[level];
00429 }
00430
00431
00432 current->removeData();
00433 delete current;
00434
00435
00436 while ( (mLevel > 1)
00437 &&(!mHead.mForward[mLevel - 1]))
00438 {
00439 mLevel--;
00440 }
00441 }
00442 return TRUE;
00443 }
00444
00445
00446 template <class DATA_TYPE, S32 BINARY_DEPTH>
00447 inline BOOL LLPtrSkipList<DATA_TYPE, BINARY_DEPTH>::moveData(const DATA_TYPE *data, LLPtrSkipList *newlist, BOOL b_sort)
00448 {
00449 BOOL removed = removeData(data);
00450 BOOL added = newlist->addData(data);
00451 return removed && added;
00452 }
00453
00454 template <class DATA_TYPE, S32 BINARY_DEPTH>
00455 inline BOOL LLPtrSkipList<DATA_TYPE, BINARY_DEPTH>::moveCurrentData(LLPtrSkipList *newlist, BOOL b_sort)
00456 {
00457 if (mCurrentOperatingp)
00458 {
00459 mCurrentp = mCurrentOperatingp->mForward[0];
00460 BOOL removed = removeData(mCurrentOperatingp);
00461 BOOL added = newlist->addData(mCurrentOperatingp);
00462 mCurrentOperatingp = mCurrentp;
00463 return removed && added;
00464 }
00465 return FALSE;
00466 }
00467
00468
00469
00470
00471
00472
00473
00474
00475
00476
00477
00478
00479
00480 template <class DATA_TYPE, S32 BINARY_DEPTH>
00481 inline void LLPtrSkipList<DATA_TYPE, BINARY_DEPTH>::removeAllNodes()
00482 {
00483 LLPtrSkipNode *temp;
00484
00485 mCurrentp = *(mHead.mForward);
00486
00487 while (mCurrentp)
00488 {
00489 temp = mCurrentp->mForward[0];
00490 mCurrentp->removeData();
00491 delete mCurrentp;
00492 mCurrentp = temp;
00493 }
00494
00495 S32 i;
00496 for (i = 0; i < BINARY_DEPTH; i++)
00497 {
00498 mHead.mForward[i] = NULL;
00499 mUpdate[i] = NULL;
00500 }
00501
00502 mCurrentp = *(mHead.mForward);
00503 mCurrentOperatingp = *(mHead.mForward);
00504 }
00505
00506 template <class DATA_TYPE, S32 BINARY_DEPTH>
00507 inline BOOL LLPtrSkipList<DATA_TYPE, BINARY_DEPTH>::deleteData(const DATA_TYPE *data)
00508 {
00509 S32 level;
00510 LLPtrSkipNode *current = &mHead;
00511 LLPtrSkipNode *temp;
00512
00513
00514 if (mInsertFirst)
00515 {
00516 for (level = mLevel - 1; level >= 0; level--)
00517 {
00518 temp = *(current->mForward + level);
00519 while ( (temp)
00520 &&(mInsertFirst(temp->mData, data)))
00521 {
00522 current = temp;
00523 temp = *(current->mForward + level);
00524 }
00525 *(mUpdate + level) = current;
00526 }
00527 }
00528 else
00529 {
00530 for (level = mLevel - 1; level >= 0; level--)
00531 {
00532 temp = *(current->mForward + level);
00533 while ( (temp)
00534 &&(temp->mData < data))
00535 {
00536 current = temp;
00537 temp = *(current->mForward + level);
00538 }
00539 *(mUpdate + level) = current;
00540 }
00541 }
00542
00543
00544
00545 current = *current->mForward;
00546
00547 if (!current)
00548 {
00549
00550 return FALSE;
00551 }
00552
00553
00554 if (!mEquals(current->mData, data))
00555 {
00556
00557 return FALSE;
00558 }
00559 else
00560 {
00561
00562 if (current == mCurrentp)
00563 {
00564 mCurrentp = current->mForward[0];
00565 }
00566
00567 if (current == mCurrentOperatingp)
00568 {
00569 mCurrentOperatingp = current->mForward[0];
00570 }
00571
00572
00573 for (level = 0; level < mLevel; level++)
00574 {
00575 if (mUpdate[level]->mForward[level] != current)
00576 {
00577
00578 break;
00579 }
00580 mUpdate[level]->mForward[level] = current->mForward[level];
00581 }
00582
00583
00584 current->deleteData();
00585 delete current;
00586
00587
00588 while ( (mLevel > 1)
00589 &&(!mHead.mForward[mLevel - 1]))
00590 {
00591 mLevel--;
00592 }
00593 }
00594 return TRUE;
00595 }
00596
00597
00598 template <class DATA_TYPE, S32 BINARY_DEPTH>
00599 inline void LLPtrSkipList<DATA_TYPE, BINARY_DEPTH>::deleteAllData()
00600 {
00601 LLPtrSkipNode *temp;
00602
00603 mCurrentp = *(mHead.mForward);
00604
00605 while (mCurrentp)
00606 {
00607 temp = mCurrentp->mForward[0];
00608 mCurrentp->deleteData();
00609 delete mCurrentp;
00610 mCurrentp = temp;
00611 }
00612
00613 S32 i;
00614 for (i = 0; i < BINARY_DEPTH; i++)
00615 {
00616 mHead.mForward[i] = NULL;
00617 mUpdate[i] = NULL;
00618 }
00619
00620 mCurrentp = *(mHead.mForward);
00621 mCurrentOperatingp = *(mHead.mForward);
00622 }
00623
00624
00625 template <class DATA_TYPE, S32 BINARY_DEPTH>
00626 inline void LLPtrSkipList<DATA_TYPE, BINARY_DEPTH>::resetList()
00627 {
00628 mCurrentp = *(mHead.mForward);
00629 mCurrentOperatingp = *(mHead.mForward);
00630 }
00631
00632
00633 template <class DATA_TYPE, S32 BINARY_DEPTH>
00634 inline DATA_TYPE *LLPtrSkipList<DATA_TYPE, BINARY_DEPTH>::getCurrentData()
00635 {
00636 if (mCurrentp)
00637 {
00638 mCurrentOperatingp = mCurrentp;
00639 mCurrentp = *mCurrentp->mForward;
00640 return mCurrentOperatingp->mData;
00641 }
00642 else
00643 {
00644
00645 return 0;
00646 }
00647 }
00648
00649
00650 template <class DATA_TYPE, S32 BINARY_DEPTH>
00651 inline DATA_TYPE *LLPtrSkipList<DATA_TYPE, BINARY_DEPTH>::getNextData()
00652 {
00653 if (mCurrentp)
00654 {
00655 mCurrentOperatingp = mCurrentp;
00656 mCurrentp = *mCurrentp->mForward;
00657 return mCurrentOperatingp->mData;
00658 }
00659 else
00660 {
00661
00662 return 0;
00663 }
00664 }
00665
00666
00667
00668 template <class DATA_TYPE, S32 BINARY_DEPTH>
00669 inline void LLPtrSkipList<DATA_TYPE, BINARY_DEPTH>::removeCurrentData()
00670 {
00671 if (mCurrentOperatingp)
00672 {
00673 removeData(mCurrentOperatingp->mData);
00674 }
00675 }
00676
00677
00678
00679 template <class DATA_TYPE, S32 BINARY_DEPTH>
00680 inline void LLPtrSkipList<DATA_TYPE, BINARY_DEPTH>::deleteCurrentData()
00681 {
00682 if (mCurrentOperatingp)
00683 {
00684 deleteData(mCurrentOperatingp->mData);
00685 }
00686 }
00687
00688
00689 template <class DATA_TYPE, S32 BINARY_DEPTH>
00690 inline DATA_TYPE *LLPtrSkipList<DATA_TYPE, BINARY_DEPTH>::getFirstData()
00691 {
00692 mCurrentp = *(mHead.mForward);
00693 mCurrentOperatingp = *(mHead.mForward);
00694 if (mCurrentp)
00695 {
00696 mCurrentOperatingp = mCurrentp;
00697 mCurrentp = mCurrentp->mForward[0];
00698 return mCurrentOperatingp->mData;
00699 }
00700 else
00701 {
00702
00703 return 0;
00704 }
00705 }
00706
00707 template <class DATA_TYPE, S32 BINARY_DEPTH>
00708 inline BOOL LLPtrSkipList<DATA_TYPE, BINARY_DEPTH>::corrupt()
00709 {
00710 LLPtrSkipNode *previous = mHead.mForward[0];
00711
00712
00713 if (!previous) return FALSE;
00714
00715 LLPtrSkipNode *current = previous->mForward[0];
00716 while(current)
00717 {
00718 if (!mInsertFirst(previous->mData, current->mData))
00719 {
00720
00721 return TRUE;
00722 }
00723 current = current->mForward[0];
00724 }
00725 return FALSE;
00726 }
00727
00728 #endif