llskipmap.h

Go to the documentation of this file.
00001 
00032 #ifndef LL_LLSKIPMAP_H
00033 #define LL_LLSKIPMAP_H
00034 
00035 #include "llerror.h"
00036 
00037 template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH = 8> 
00038 class LLSkipMap
00039 {
00040 public:
00041         // basic constructor
00042         LLSkipMap();
00043 
00044         // basic constructor including sorter
00045         LLSkipMap(BOOL  (*insert_first)(const INDEX_TYPE &first, const INDEX_TYPE &second), 
00046                            BOOL (*equals)(const INDEX_TYPE &first, const INDEX_TYPE &second));
00047 
00048         ~LLSkipMap();
00049 
00050         void setInsertFirst(BOOL (*insert_first)(const INDEX_TYPE &first, const INDEX_TYPE &second));
00051         void setEquals(BOOL (*equals)(const INDEX_TYPE &first, const INDEX_TYPE &second));
00052 
00053         DATA_TYPE &addData(const INDEX_TYPE &index, DATA_TYPE datap);
00054         DATA_TYPE &addData(const INDEX_TYPE &index);
00055         DATA_TYPE &getData(const INDEX_TYPE &index);
00056         DATA_TYPE &operator[](const INDEX_TYPE &index);
00057 
00058         // If index present, returns data.
00059         // If index not present, adds <index,NULL> and returns NULL.
00060         DATA_TYPE &getData(const INDEX_TYPE &index, BOOL &b_new_entry);
00061 
00062         // Returns TRUE if data present in map.
00063         BOOL checkData(const INDEX_TYPE &index);
00064 
00065         // Returns TRUE if key is present in map. This is useful if you
00066         // are potentially storing NULL pointers in the map
00067         BOOL checkKey(const INDEX_TYPE &index);
00068 
00069         // If there, returns the data.
00070         // If not, returns NULL.
00071         // Never adds entries to the map.
00072         DATA_TYPE getIfThere(const INDEX_TYPE &index);
00073 
00074         INDEX_TYPE reverseLookup(const DATA_TYPE datap);
00075 
00076         // returns number of items in the list
00077         S32 getLength(); // WARNING!  getLength is O(n), not O(1)!
00078 
00079         BOOL removeData(const INDEX_TYPE &index);
00080 
00081         // remove all nodes from the list but do not delete data
00082         void removeAllData();
00083 
00084         // place mCurrentp on first node
00085         void resetList();
00086 
00087         // return the data currently pointed to
00088         DATA_TYPE       getCurrentDataWithoutIncrement();
00089 
00090         // return the data currently pointed to, set mCurentOperatingp to that node and bump mCurrentp
00091         DATA_TYPE       getCurrentData();
00092 
00093         // same as getCurrentData() but a more intuitive name for the operation
00094         DATA_TYPE       getNextData();
00095 
00096         INDEX_TYPE      getNextKey();
00097 
00098         // return the key currently pointed to
00099         INDEX_TYPE      getCurrentKeyWithoutIncrement();
00100 
00101         // The internal iterator is at the end of the list.
00102         BOOL            notDone() const;
00103 
00104         // remove the Node at mCurentOperatingp
00105         // leave mCurrentp and mCurentOperatingp on the next entry
00106         void removeCurrentData();
00107 
00108         void deleteCurrentData();
00109 
00110         // reset the list and return the data currently pointed to, set mCurentOperatingp to that node and bump mCurrentp
00111         DATA_TYPE       getFirstData();
00112 
00113         INDEX_TYPE      getFirstKey();
00114 
00115         class LLSkipMapNode
00116         {
00117         public:
00118                 LLSkipMapNode()
00119                 {
00120                         S32 i;
00121                         for (i = 0; i < BINARY_DEPTH; i++)
00122                         {
00123                                 mForward[i] = NULL;
00124                         }
00125 
00126                         U8  *zero = (U8 *)&mIndex;
00127 
00128                         for (i = 0; i < (S32)sizeof(INDEX_TYPE); i++)
00129                         {
00130                                 *(zero + i) = 0;
00131                         }
00132 
00133                         zero = (U8 *)&mData;
00134 
00135                         for (i = 0; i < (S32)sizeof(DATA_TYPE); i++)
00136                         {
00137                                 *(zero + i) = 0;
00138                         }
00139                 }
00140 
00141                 LLSkipMapNode(const INDEX_TYPE &index)
00142                 :       mIndex(index)
00143                 {
00144 
00145                         S32 i;
00146                         for (i = 0; i < BINARY_DEPTH; i++)
00147                         {
00148                                 mForward[i] = NULL;
00149                         }
00150 
00151                         U8 *zero = (U8 *)&mData;
00152 
00153                         for (i = 0; i < (S32)sizeof(DATA_TYPE); i++)
00154                         {
00155                                 *(zero + i) = 0;
00156                         }
00157                 }
00158 
00159                 LLSkipMapNode(const INDEX_TYPE &index, DATA_TYPE datap)
00160                 :       mIndex(index)
00161                 {
00162 
00163                         S32 i;
00164                         for (i = 0; i < BINARY_DEPTH; i++)
00165                         {
00166                                 mForward[i] = NULL;
00167                         }
00168 
00169                         mData = datap;
00170                 }
00171 
00172                 ~LLSkipMapNode()
00173                 {
00174                 }
00175 
00176 
00177                 INDEX_TYPE                                      mIndex;
00178                 DATA_TYPE                                       mData;
00179                 LLSkipMapNode                           *mForward[BINARY_DEPTH];
00180 
00181         private:
00182                 // Disallow copying of LLSkipMapNodes by not implementing these methods.
00183                 LLSkipMapNode(const LLSkipMapNode &);
00184                 LLSkipMapNode &operator=(const LLSkipMapNode &rhs);
00185         };
00186 
00187         static BOOL     defaultEquals(const INDEX_TYPE &first, const INDEX_TYPE &second)
00188         {
00189                 return first == second;
00190         }
00191 
00192 private:
00193         // don't generate implicit copy constructor or copy assignment
00194         LLSkipMap(const LLSkipMap &);
00195         LLSkipMap &operator=(const LLSkipMap &);
00196 
00197 private:
00198         LLSkipMapNode                           mHead;
00199         LLSkipMapNode                           *mUpdate[BINARY_DEPTH];
00200         LLSkipMapNode                           *mCurrentp;
00201         LLSkipMapNode                           *mCurrentOperatingp;
00202         S32                                                     mLevel;
00203         BOOL                                            (*mInsertFirst)(const INDEX_TYPE &first, const INDEX_TYPE &second);
00204         BOOL                                            (*mEquals)(const INDEX_TYPE &first, const INDEX_TYPE &second);
00205         S32                                                     mNumberOfSteps;
00206 };
00207 
00209 //
00210 // LLSkipMap implementation
00211 //
00212 
00213 template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
00214 inline LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::LLSkipMap()
00215         :       mInsertFirst(NULL),
00216                 mEquals(defaultEquals)
00217 {
00218         // Skipmaps must have binary depth of at least 2
00219         cassert(BINARY_DEPTH >= 2);
00220 
00221         S32 i;
00222         for (i = 0; i < BINARY_DEPTH; i++)
00223         {
00224                 mUpdate[i] = NULL;
00225         }
00226         mLevel = 1;
00227         mCurrentp = *(mHead.mForward);
00228         mCurrentOperatingp = *(mHead.mForward);
00229 }
00230 
00231 template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
00232 inline LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::LLSkipMap(BOOL   (*insert_first)(const INDEX_TYPE &first, const INDEX_TYPE &second), 
00233                            BOOL (*equals)(const INDEX_TYPE &first, const INDEX_TYPE &second)) 
00234         :       mInsertFirst(insert_first),
00235                 mEquals(equals)
00236 {
00237         // Skipmaps must have binary depth of at least 2
00238         cassert(BINARY_DEPTH >= 2);
00239 
00240         mLevel = 1;
00241         S32 i;
00242         for (i = 0; i < BINARY_DEPTH; i++)
00243         {
00244                 mHead.mForward[i] = NULL;
00245                 mUpdate[i] = NULL;
00246         }
00247         mCurrentp = *(mHead.mForward);
00248         mCurrentOperatingp = *(mHead.mForward);
00249 }
00250 
00251 template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
00252 inline LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::~LLSkipMap()
00253 {
00254         removeAllData();
00255 }
00256 
00257 template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
00258 inline void LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::setInsertFirst(BOOL (*insert_first)(const INDEX_TYPE &first, const INDEX_TYPE &second))
00259 {
00260         mInsertFirst = insert_first;
00261 }
00262 
00263 template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
00264 inline void LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::setEquals(BOOL (*equals)(const INDEX_TYPE &first, const INDEX_TYPE &second))
00265 {
00266         mEquals = equals;
00267 }
00268 
00269 template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
00270 inline DATA_TYPE &LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::addData(const INDEX_TYPE &index, DATA_TYPE datap)
00271 {
00272         S32                     level;
00273         LLSkipMapNode   *current = &mHead;
00274         LLSkipMapNode   *temp;
00275 
00276         // find the pointer one in front of the one we want
00277         if (mInsertFirst)
00278         {
00279                 for (level = mLevel - 1; level >= 0; level--)
00280                 {
00281                         temp = *(current->mForward + level);
00282                         while (  (temp)
00283                                    &&(mInsertFirst(temp->mIndex, index)))
00284                         {
00285                                 current = temp;
00286                                 temp = *(current->mForward + level);
00287                         }
00288                         *(mUpdate + level) = current;
00289                 }
00290         }
00291         else
00292         {
00293                 for (level = mLevel - 1; level >= 0; level--)
00294                 {
00295                         temp = *(current->mForward + level);
00296                         while (  (temp)
00297                                    &&(temp->mIndex < index))
00298                         {
00299                                 current = temp;
00300                                 temp = *(current->mForward + level);
00301                         }
00302                         *(mUpdate + level) = current;
00303                 }
00304         }
00305         
00306         // we're now just in front of where we want to be . . . take one step forward
00307         current = *current->mForward;
00308 
00309         // replace the existing data if a node is already there
00310         if (  (current)
00311                 &&(mEquals(current->mIndex, index)))
00312         {
00313                 current->mData = datap;
00314                 return current->mData;
00315         }
00316 
00317         // now add the new node
00318         S32 newlevel;
00319         for (newlevel = 1; newlevel <= mLevel && newlevel < BINARY_DEPTH; newlevel++)
00320         {
00321                 if (rand() & 1)
00322                 {
00323                         break;
00324                 }
00325         }
00326 
00327         LLSkipMapNode *snode = new LLSkipMapNode(index, datap);
00328 
00329         if (newlevel > mLevel)
00330         {
00331                 mHead.mForward[mLevel] = NULL;
00332                 mUpdate[mLevel] = &mHead;
00333                 mLevel = newlevel;
00334         }
00335 
00336         for (level = 0; level < newlevel; level++)
00337         {
00338                 snode->mForward[level] = mUpdate[level]->mForward[level];
00339                 mUpdate[level]->mForward[level] = snode;
00340         }
00341         return snode->mData;
00342 }
00343 
00344 template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
00345 inline DATA_TYPE &LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::addData(const INDEX_TYPE &index)
00346 {
00347         S32                     level;
00348         LLSkipMapNode   *current = &mHead;
00349         LLSkipMapNode   *temp;
00350 
00351         // find the pointer one in front of the one we want
00352         if (mInsertFirst)
00353         {
00354                 for (level = mLevel - 1; level >= 0; level--)
00355                 {
00356                         temp = *(current->mForward + level);
00357                         while (  (temp)
00358                                    &&(mInsertFirst(temp->mIndex, index)))
00359                         {
00360                                 current = temp;
00361                                 temp = *(current->mForward + level);
00362                         }
00363                         *(mUpdate + level) = current;
00364                 }
00365         }
00366         else
00367         {
00368                 for (level = mLevel - 1; level >= 0; level--)
00369                 {
00370                         temp = *(current->mForward + level);
00371                         while (  (temp)
00372                                    &&(temp->mIndex < index))
00373                         {
00374                                 current = temp;
00375                                 temp = *(current->mForward + level);
00376                         }
00377                         *(mUpdate + level) = current;
00378                 }
00379         }
00380         
00381         // we're now just in front of where we want to be . . . take one step forward
00382         current = *current->mForward;
00383 
00384         // now add the new node
00385         S32 newlevel;
00386         for (newlevel = 1; newlevel <= mLevel && newlevel < BINARY_DEPTH; newlevel++)
00387         {
00388                 if (rand() & 1)
00389                         break;
00390         }
00391 
00392         LLSkipMapNode *snode = new LLSkipMapNode(index);
00393 
00394         if (newlevel > mLevel)
00395         {
00396                 mHead.mForward[mLevel] = NULL;
00397                 mUpdate[mLevel] = &mHead;
00398                 mLevel = newlevel;
00399         }
00400 
00401         for (level = 0; level < newlevel; level++)
00402         {
00403                 snode->mForward[level] = mUpdate[level]->mForward[level];
00404                 mUpdate[level]->mForward[level] = snode;
00405         }
00406         return snode->mData;
00407 }
00408 
00409 template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
00410 inline DATA_TYPE &LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::getData(const INDEX_TYPE &index)
00411 {
00412         S32                     level;
00413         LLSkipMapNode   *current = &mHead;
00414         LLSkipMapNode   *temp;
00415 
00416         mNumberOfSteps = 0;
00417 
00418         // find the pointer one in front of the one we want
00419         if (mInsertFirst)
00420         {
00421                 for (level = mLevel - 1; level >= 0; level--)
00422                 {
00423                         temp = *(current->mForward + level);
00424                         while (  (temp)
00425                                    &&(mInsertFirst(temp->mIndex, index)))
00426                         {
00427                                 current = temp;
00428                                 temp = *(current->mForward + level);
00429                                 mNumberOfSteps++;
00430                         }
00431                         *(mUpdate + level) = current;
00432                 }
00433         }
00434         else
00435         {
00436                 for (level = mLevel - 1; level >= 0; level--)
00437                 {
00438                         temp = *(current->mForward + level);
00439                         while (  (temp)
00440                                    &&(temp->mIndex < index))
00441                         {
00442                                 current = temp;
00443                                 temp = *(current->mForward + level);
00444                                 mNumberOfSteps++;
00445                         }
00446                         *(mUpdate + level) = current;
00447                 }
00448         }
00449         
00450         // we're now just in front of where we want to be . . . take one step forward
00451         current = *current->mForward;
00452         mNumberOfSteps++;
00453 
00454         if (  (current)
00455                 &&(mEquals(current->mIndex, index)))
00456         {
00457                 
00458                 return current->mData;
00459         }
00460         
00461         // now add the new node
00462         S32 newlevel;
00463         for (newlevel = 1; newlevel <= mLevel && newlevel < BINARY_DEPTH; newlevel++)
00464         {
00465                 if (rand() & 1)
00466                         break;
00467         }
00468 
00469         LLSkipMapNode *snode = new LLSkipMapNode(index);
00470 
00471         if (newlevel > mLevel)
00472         {
00473                 mHead.mForward[mLevel] = NULL;
00474                 mUpdate[mLevel] = &mHead;
00475                 mLevel = newlevel;
00476         }
00477 
00478         for (level = 0; level < newlevel; level++)
00479         {
00480                 snode->mForward[level] = mUpdate[level]->mForward[level];
00481                 mUpdate[level]->mForward[level] = snode;
00482         }
00483         
00484         return snode->mData;
00485 }
00486 
00487 template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
00488 inline DATA_TYPE &LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::operator[](const INDEX_TYPE &index)
00489 {
00490         
00491         return getData(index);
00492 }
00493 
00494 // If index present, returns data.
00495 // If index not present, adds <index,NULL> and returns NULL.
00496 template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
00497 inline DATA_TYPE &LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::getData(const INDEX_TYPE &index, BOOL &b_new_entry)
00498 {
00499         S32                     level;
00500         LLSkipMapNode   *current = &mHead;
00501         LLSkipMapNode   *temp;
00502 
00503         mNumberOfSteps = 0;
00504 
00505         // find the pointer one in front of the one we want
00506         if (mInsertFirst)
00507         {
00508                 for (level = mLevel - 1; level >= 0; level--)
00509                 {
00510                         temp = *(current->mForward + level);
00511                         while (  (temp)
00512                                    &&(mInsertFirst(temp->mIndex, index)))
00513                         {
00514                                 current = temp;
00515                                 temp = *(current->mForward + level);
00516                                 mNumberOfSteps++;
00517                         }
00518                         *(mUpdate + level) = current;
00519                 }
00520         }
00521         else
00522         {
00523                 for (level = mLevel - 1; level >= 0; level--)
00524                 {
00525                         temp = *(current->mForward + level);
00526                         while (  (temp)
00527                                    &&(temp->mIndex < index))
00528                         {
00529                                 current = temp;
00530                                 temp = *(current->mForward + level);
00531                                 mNumberOfSteps++;
00532                         }
00533                         *(mUpdate + level) = current;
00534                 }
00535         }
00536         
00537         // we're now just in front of where we want to be . . . take one step forward
00538         mNumberOfSteps++;
00539         current = *current->mForward;
00540 
00541         if (  (current)
00542                 &&(mEquals(current->mIndex, index)))
00543         {
00544                 
00545                 return current->mData;
00546         }
00547         b_new_entry = TRUE;
00548         addData(index);
00549         
00550         return current->mData;
00551 }
00552 
00553 // Returns TRUE if data present in map.
00554 template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
00555 inline BOOL LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::checkData(const INDEX_TYPE &index)
00556 {
00557         S32                     level;
00558         LLSkipMapNode   *current = &mHead;
00559         LLSkipMapNode   *temp;
00560 
00561         // find the pointer one in front of the one we want
00562         if (mInsertFirst)
00563         {
00564                 for (level = mLevel - 1; level >= 0; level--)
00565                 {
00566                         temp = *(current->mForward + level);
00567                         while (  (temp)
00568                                    &&(mInsertFirst(temp->mIndex, index)))
00569                         {
00570                                 current = temp;
00571                                 temp = *(current->mForward + level);
00572                         }
00573                         *(mUpdate + level) = current;
00574                 }
00575         }
00576         else
00577         {
00578                 for (level = mLevel - 1; level >= 0; level--)
00579                 {
00580                         temp = *(current->mForward + level);
00581                         while (  (temp)
00582                                    &&(temp->mIndex < index))
00583                         {
00584                                 current = temp;
00585                                 temp = *(current->mForward + level);
00586                         }
00587                         *(mUpdate + level) = current;
00588                 }
00589         }
00590         
00591         // we're now just in front of where we want to be . . . take one step forward
00592         current = *current->mForward;
00593 
00594         if (current)
00595         {
00596                 // Gets rid of some compiler ambiguity for the LLPointer<> templated class.
00597                 if (current->mData)
00598                 {
00599                         return mEquals(current->mIndex, index);
00600                 }
00601         }
00602 
00603         return FALSE;
00604 }
00605 
00606 // Returns TRUE if key is present in map. This is useful if you
00607 // are potentially storing NULL pointers in the map
00608 template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
00609 inline BOOL LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::checkKey(const INDEX_TYPE &index)
00610 {
00611         S32                     level;
00612         LLSkipMapNode   *current = &mHead;
00613         LLSkipMapNode   *temp;
00614 
00615         // find the pointer one in front of the one we want
00616         if (mInsertFirst)
00617         {
00618                 for (level = mLevel - 1; level >= 0; level--)
00619                 {
00620                         temp = *(current->mForward + level);
00621                         while (  (temp)
00622                                    &&(mInsertFirst(temp->mIndex, index)))
00623                         {
00624                                 current = temp;
00625                                 temp = *(current->mForward + level);
00626                         }
00627                         *(mUpdate + level) = current;
00628                 }
00629         }
00630         else
00631         {
00632                 for (level = mLevel - 1; level >= 0; level--)
00633                 {
00634                         temp = *(current->mForward + level);
00635                         while (  (temp)
00636                                    &&(temp->mIndex < index))
00637                         {
00638                                 current = temp;
00639                                 temp = *(current->mForward + level);
00640                         }
00641                         *(mUpdate + level) = current;
00642                 }
00643         }
00644         
00645         // we're now just in front of where we want to be . . . take one step forward
00646         current = *current->mForward;
00647 
00648         if (current)
00649         {
00650                 return mEquals(current->mIndex, index);
00651         }
00652 
00653         return FALSE;
00654 }
00655 
00656 // If there, returns the data.
00657 // If not, returns NULL.
00658 // Never adds entries to the map.
00659 template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
00660 inline DATA_TYPE LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::getIfThere(const INDEX_TYPE &index)
00661 {
00662         S32                     level;
00663         LLSkipMapNode   *current = &mHead;
00664         LLSkipMapNode   *temp;
00665 
00666         mNumberOfSteps = 0;
00667 
00668         // find the pointer one in front of the one we want
00669         if (mInsertFirst)
00670         {
00671                 for (level = mLevel - 1; level >= 0; level--)
00672                 {
00673                         temp = *(current->mForward + level);
00674                         while (  (temp)
00675                                    &&(mInsertFirst(temp->mIndex, index)))
00676                         {
00677                                 current = temp;
00678                                 temp = *(current->mForward + level);
00679                                 mNumberOfSteps++;
00680                         }
00681                         *(mUpdate + level) = current;
00682                 }
00683         }
00684         else
00685         {
00686                 for (level = mLevel - 1; level >= 0; level--)
00687                 {
00688                         temp = *(current->mForward + level);
00689                         while (  (temp)
00690                                    &&(temp->mIndex < index))
00691                         {
00692                                 current = temp;
00693                                 temp = *(current->mForward + level);
00694                                 mNumberOfSteps++;
00695                         }
00696                         *(mUpdate + level) = current;
00697                 }
00698         }
00699         
00700         // we're now just in front of where we want to be . . . take one step forward
00701         mNumberOfSteps++;
00702         current = *current->mForward;
00703 
00704         if (current)
00705         {
00706                 if (mEquals(current->mIndex, index))
00707                 {
00708                         return current->mData;
00709                 }
00710         }
00711 
00712         // Avoid Linux compiler warning on returning NULL.
00713         return DATA_TYPE();
00714 }
00715 
00716 template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
00717 inline INDEX_TYPE LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::reverseLookup(const DATA_TYPE datap)
00718 {
00719         LLSkipMapNode   *current = &mHead;
00720 
00721         while (current)
00722         {
00723                 if (datap == current->mData)
00724                 {
00725                         
00726                         return current->mIndex;
00727                 }
00728                 current = *current->mForward;
00729         }
00730 
00731         // not found! return NULL
00732         return INDEX_TYPE();
00733 }
00734 
00735 // returns number of items in the list
00736 template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
00737 inline S32 LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::getLength()
00738 {
00739         U32     length = 0;
00740         for (LLSkipMapNode* temp = *(mHead.mForward); temp != NULL; temp = temp->mForward[0])
00741         {
00742                 length++;
00743         }
00744         
00745         return length;
00746 }
00747 
00748 template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
00749 inline BOOL LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::removeData(const INDEX_TYPE &index)
00750 {
00751         S32                     level;
00752         LLSkipMapNode   *current = &mHead;
00753         LLSkipMapNode   *temp;
00754 
00755         // find the pointer one in front of the one we want
00756         if (mInsertFirst)
00757         {
00758                 for (level = mLevel - 1; level >= 0; level--)
00759                 {
00760                         temp = *(current->mForward + level);
00761                         while (  (temp)
00762                                    &&(mInsertFirst(temp->mIndex, index)))
00763                         {
00764                                 current = temp;
00765                                 temp = *(current->mForward + level);
00766                         }
00767                         *(mUpdate + level) = current;
00768                 }
00769         }
00770         else
00771         {
00772                 for (level = mLevel - 1; level >= 0; level--)
00773                 {
00774                         temp = *(current->mForward + level);
00775                         while (  (temp)
00776                                    &&(temp->mIndex < index))
00777                         {
00778                                 current = temp;
00779                                 temp = *(current->mForward + level);
00780                         }
00781                         *(mUpdate + level) = current;
00782                 }
00783         }
00784         
00785         // we're now just in front of where we want to be . . . take one step forward
00786         current = *current->mForward;
00787 
00788         if (!current)
00789         {
00790                 // empty list or beyond the end!
00791                 
00792                 return FALSE;
00793         }
00794 
00795         // is this the one we want?
00796         if (!mEquals(current->mIndex, index))
00797         {
00798                 // nope!
00799                 
00800                 return FALSE;
00801         }
00802         else
00803         {
00804                 // do we need to fix current or currentop?
00805                 if (current == mCurrentp)
00806                 {
00807                         mCurrentp = *current->mForward;
00808                 }
00809 
00810                 if (current == mCurrentOperatingp)
00811                 {
00812                         mCurrentOperatingp = *current->mForward;
00813                 }
00814                 // yes it is!  change pointers as required
00815                 for (level = 0; level < mLevel; level++)
00816                 {
00817                         if (*((*(mUpdate + level))->mForward + level) != current)
00818                         {
00819                                 // cool, we've fixed all the pointers!
00820                                 break;
00821                         }
00822                         *((*(mUpdate + level))->mForward + level) = *(current->mForward + level);
00823                 }
00824 
00825                 delete current;
00826 
00827                 // clean up mHead
00828                 while (  (mLevel > 1)
00829                            &&(!*(mHead.mForward + mLevel - 1)))
00830                 {
00831                         mLevel--;
00832                 }
00833         }
00834         
00835         return TRUE;
00836 }
00837 
00838 
00839 // remove all nodes from the list but do not delete data
00840 template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
00841 void LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::removeAllData()
00842 {
00843         LLSkipMapNode *temp;
00844         // reset mCurrentp
00845         mCurrentp = *(mHead.mForward);
00846 
00847         while (mCurrentp)
00848         {
00849                 temp = mCurrentp->mForward[0];
00850                 delete mCurrentp;
00851                 mCurrentp = temp;
00852         }
00853 
00854         S32 i;
00855         for (i = 0; i < BINARY_DEPTH; i++)
00856         {
00857                 mHead.mForward[i] = NULL;
00858                 mUpdate[i] = NULL;
00859         }
00860 
00861         mCurrentp = *(mHead.mForward);
00862         mCurrentOperatingp = *(mHead.mForward);
00863 }
00864 
00865 
00866 // place mCurrentp on first node
00867 template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
00868 inline void LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::resetList()
00869 {
00870         mCurrentp = *(mHead.mForward);
00871         mCurrentOperatingp = *(mHead.mForward);
00872 }
00873 
00874 
00875 // return the data currently pointed to
00876 template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
00877 inline DATA_TYPE LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::getCurrentDataWithoutIncrement()
00878 {
00879         if (mCurrentOperatingp)
00880         {
00881                 return mCurrentOperatingp->mData;
00882         }
00883         else
00884         {
00885                 return DATA_TYPE();
00886         }
00887 }
00888 
00889 // return the data currently pointed to, set mCurentOperatingp to that node and bump mCurrentp
00890 template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
00891 inline DATA_TYPE LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::getCurrentData()
00892 {
00893         if (mCurrentp)
00894         {
00895                 mCurrentOperatingp = mCurrentp;
00896                 mCurrentp = mCurrentp->mForward[0];
00897                 return mCurrentOperatingp->mData;
00898         }
00899         else
00900         {
00901                 // Basic types, like int, have default constructors that initialize
00902                 // them to zero.  g++ 2.95 supports this.  "int()" is zero.
00903                 // This also is nice for LLUUID()
00904                 return DATA_TYPE();
00905         }
00906 }
00907 
00908 // same as getCurrentData() but a more intuitive name for the operation
00909 template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
00910 inline DATA_TYPE LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::getNextData()
00911 {
00912         if (mCurrentp)
00913         {
00914                 mCurrentOperatingp = mCurrentp;
00915                 mCurrentp = mCurrentp->mForward[0];
00916                 return mCurrentOperatingp->mData;
00917         }
00918         else
00919         {
00920                 // Basic types, like int, have default constructors that initialize
00921                 // them to zero.  g++ 2.95 supports this.  "int()" is zero.
00922                 // This also is nice for LLUUID()
00923                 return DATA_TYPE();
00924         }
00925 }
00926 
00927 template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
00928 inline INDEX_TYPE LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::getNextKey()
00929 {
00930         if (mCurrentp)
00931         {
00932                 mCurrentOperatingp = mCurrentp;
00933                 mCurrentp = mCurrentp->mForward[0];
00934                 return mCurrentOperatingp->mIndex;
00935         }
00936         else
00937         {
00938                 return mHead.mIndex;
00939         }
00940 }
00941 
00942 // return the key currently pointed to
00943 template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
00944 inline INDEX_TYPE LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::getCurrentKeyWithoutIncrement()
00945 {
00946         if (mCurrentOperatingp)
00947         {
00948                 return mCurrentOperatingp->mIndex;
00949         }
00950         else
00951         {
00952                 // See comment for getNextData()
00953                 return INDEX_TYPE();
00954         }
00955 }
00956 
00957 template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
00958 inline BOOL LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::notDone() const
00959 {
00960         if (mCurrentOperatingp)
00961         {
00962                 return TRUE;
00963         }
00964         else
00965         {
00966                 return FALSE;
00967         }
00968 }
00969 
00970 
00971 // remove the Node at mCurentOperatingp
00972 // leave mCurrentp and mCurentOperatingp on the next entry
00973 template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
00974 inline void LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::removeCurrentData()
00975 {
00976         if (mCurrentOperatingp)
00977         {
00978                 removeData(mCurrentOperatingp->mIndex);
00979         }
00980 }
00981 
00982 template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
00983 inline void LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::deleteCurrentData()
00984 {
00985         if (mCurrentOperatingp)
00986         {
00987                 deleteData(mCurrentOperatingp->mIndex);
00988         }
00989 }
00990 
00991 // reset the list and return the data currently pointed to, set mCurentOperatingp to that node and bump mCurrentp
00992 template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
00993 inline DATA_TYPE LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::getFirstData()
00994 {
00995         mCurrentp = *(mHead.mForward);
00996         mCurrentOperatingp = *(mHead.mForward);
00997         if (mCurrentp)
00998         {
00999                 mCurrentOperatingp = mCurrentp;
01000                 mCurrentp = mCurrentp->mForward[0];
01001                 return mCurrentOperatingp->mData;
01002         }
01003         else
01004         {
01005                 // See comment for getNextData()
01006                 return DATA_TYPE();
01007         }
01008 }
01009 
01010 template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
01011 inline INDEX_TYPE LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::getFirstKey()
01012 {
01013         mCurrentp = *(mHead.mForward);
01014         mCurrentOperatingp = *(mHead.mForward);
01015         if (mCurrentp)
01016         {
01017                 mCurrentOperatingp = mCurrentp;
01018                 mCurrentp = mCurrentp->mForward[0];
01019                 return mCurrentOperatingp->mIndex;
01020         }
01021         else
01022         {
01023                 return mHead.mIndex;
01024         }
01025 }
01026 
01027 #endif

Generated on Thu Jul 1 06:09:11 2010 for Second Life Viewer by  doxygen 1.4.7