SkipList.h

Go to the documentation of this file.
00001 //
00002 //  Copyright (c) 2003-2006 by Autodesk, Inc.
00003 //
00004 //  By using this code, you are agreeing to the terms and conditions of
00005 //  the License Agreement included in the documentation for this code.
00006 //
00007 //  AUTODESK MAKES NO WARRANTIES, EXPRESS OR IMPLIED,
00008 //  AS TO THE CORRECTNESS OF THIS CODE OR ANY DERIVATIVE
00009 //  WORKS WHICH INCORPORATE IT.
00010 //
00011 //  AUTODESK PROVIDES THE CODE ON AN "AS-IS" BASIS
00012 //  AND EXPLICITLY DISCLAIMS ANY LIABILITY, INCLUDING
00013 //  CONSEQUENTIAL AND INCIDENTAL DAMAGES FOR ERRORS,
00014 //  OMISSIONS, AND OTHER PROBLEMS IN THE CODE.
00015 //
00016 //  Use, duplication, or disclosure by the U.S. Government is subject to
00017 //  restrictions set forth in FAR 52.227-19 (Commercial Computer Software
00018 //  Restricted Rights) and DFAR 252.227-7013(c)(1)(ii) (Rights in Technical
00019 //  Data and Computer Software), as applicable.
00020 //
00021 
00022 #ifndef _DWFCORE_SKIPLIST_H
00023 #define _DWFCORE_SKIPLIST_H
00024 
00025 
00031 
00032 
00033 #include "dwfcore/STL.h"
00034 #include "dwfcore/Hash.h"
00035 #include "dwfcore/Timer.h"
00036 #include "dwfcore/Iterator.h"
00037 #include "dwfcore/Comparator.h"
00038 
00039 
00040     
00041 
00042 #ifndef DWFCORE_SKIPLIST_PROBABILITY_DISTRIB
00054 #define DWFCORE_SKIPLIST_PROBABILITY_DISTRIB    0.5f
00055 #endif
00056 
00057 #ifndef DWFCORE_SKIPLIST_MAX_NODE_LEVEL
00065 #define DWFCORE_SKIPLIST_MAX_NODE_LEVEL         31
00066 #endif
00067 
00068 #ifndef DWFCORE_SKIPLIST_INITIAL_HEIGHT
00077 #define DWFCORE_SKIPLIST_INITIAL_HEIGHT        5
00078 #endif
00079 
00080 
00081 namespace DWFCore
00082 {
00083 
00084 
00105 template < class K, class V, class E = tDWFCompareEqual<K>, class L = tDWFCompareLess<K>, class Z = tDWFDefinedEmpty<K> >
00106 class DWFSkipList : virtual public DWFCoreMemory
00107 {
00108 
00109 public:
00110 
00114     typedef K       KeyType;
00118     typedef V       ValueType;
00119 
00120 public:
00121 
00127     DWFSkipList()
00128         throw( DWFMemoryException )
00129         : _pHeader( NULL )
00130         , _nMaxHeight( DWFCORE_SKIPLIST_INITIAL_HEIGHT )
00131         , _nMaxLevel( 0 )
00132         , _nCount( 0 )
00133     {
00134         _pHeader = DWFCORE_ALLOC_OBJECT( _Node(DWFCORE_SKIPLIST_MAX_NODE_LEVEL) );
00135         if (_pHeader == NULL)
00136         {
00137             _DWFCORE_THROW( DWFMemoryException, /*NOXLATE*/L"Failed to allocate header node" );
00138         }
00139     }
00140 
00146     virtual ~DWFSkipList()
00147         throw()
00148     {
00149         _Node* pNext = NULL;
00150         typename _Node::_Iterator iNode( _pHeader->forward(0) );
00151 
00152         while (iNode.valid())
00153         {
00154             pNext = iNode.get();
00155             iNode.next();
00156 
00157             DWFCORE_FREE_OBJECT( pNext );
00158         }
00159 
00160         DWFCORE_FREE_OBJECT( _pHeader );
00161     }
00162 
00163     //
00164     // Inner class definitions
00165     //
00166 private:
00167 
00168     class _Node : virtual public DWFCoreMemory
00169     {
00170 
00171     public:
00172 
00173         class _Iterator : public DWFIterator<_Node*>
00174                         , virtual public DWFCoreMemory
00175         {
00176         
00177         public:
00178 
00179             _Iterator( _Node* pFirst )
00180                 throw()
00181                 : _pFirst( pFirst )
00182                 , _pNext( pFirst )
00183             {;}
00184 
00185             virtual ~_Iterator()
00186                 throw()
00187             {;}
00188 
00189             void reset()
00190                 throw()
00191             {
00192                 _pNext = _pFirst;
00193             }
00194 
00195             bool valid()
00196                 throw()
00197             {
00198                 return (_pNext != NULL);
00199             }
00200 
00201             bool next()
00202                 throw()
00203             {
00204                 _pNext = _pNext->forward( 0 );
00205                 
00206                 return valid();
00207             }
00208             
00209             _Node*& get()
00210                 throw()
00211             {
00212                 return _pNext;
00213             }
00214 
00215         private:
00216 
00217             _Node* _pFirst;
00218             _Node* _pNext;
00219         };
00220 
00221         class _ConstIterator : public DWFIterator<_Node const*>
00222                              , virtual public DWFCoreMemory
00223         {
00224         
00225         public:
00226 
00227             _ConstIterator( _Node const* pFirst )
00228                 throw()
00229                 : _pFirst( pFirst )
00230                 , _pNext( pFirst )
00231             {;}
00232 
00233             virtual ~_ConstIterator()
00234                 throw()
00235             {;}
00236 
00237             void reset()
00238                 throw()
00239             {
00240                 _pNext = _pFirst;
00241             }
00242 
00243             bool valid()
00244                 throw()
00245             {
00246                 return (_pNext != NULL);
00247             }
00248 
00249             bool next()
00250                 throw()
00251             {
00252                 _pNext = _pNext->forward( 0 );
00253                 
00254                 return valid();
00255             }
00256             
00257             _Node const*& get()
00258                 throw( DWFException )
00259             {
00260                 return _pNext;
00261             }
00262 
00263         private:
00264 
00265             _Node const* _pFirst;
00266             _Node const* _pNext;
00267         };
00268 
00269     public:
00270 
00271         _Node( int nHeight )
00272             throw( DWFMemoryException )
00273             : _ppForward( NULL )
00274         {
00275             _ppForward = DWFCORE_ALLOC_MEMORY( _Node*, (nHeight + 1) );
00276 
00277             if (_ppForward == NULL)
00278             {
00279                 _DWFCORE_THROW( DWFMemoryException, /*NOXLATE*/L"Failed to allocate array" );
00280             }
00281 
00282             DWFCORE_ZERO_MEMORY( _ppForward, sizeof(_Node*) * (nHeight + 1) );
00283 
00284             Z fNull;
00285             _Key = fNull();
00286         }
00287 
00288         _Node( int      nHeight,
00289                const K& rKey,
00290                const V& rValue )
00291             throw( DWFMemoryException )
00292             : _ppForward( NULL )
00293             , _Key( rKey )
00294             , _Value( rValue )
00295         {
00296             _ppForward = DWFCORE_ALLOC_MEMORY( _Node*, (nHeight + 1) );
00297 
00298             if (_ppForward == NULL)
00299             {
00300                 _DWFCORE_THROW( DWFMemoryException, /*NOXLATE*/L"Failed to allocate array" );
00301             }
00302 
00303             DWFCORE_ZERO_MEMORY( _ppForward, sizeof(_Node*) * (nHeight + 1) );
00304         }
00305 
00306         ~_Node()
00307             throw()
00308         {
00309             if (_ppForward)
00310             {
00311                 DWFCORE_FREE_MEMORY( _ppForward );
00312             }
00313         }
00314 
00315         _Node* forward( uint16_t iLevel )
00316             throw()
00317         {
00318             return (_ppForward ? _ppForward[iLevel] : NULL);
00319         }
00320 
00321         _Node const* forward( uint16_t iLevel ) const
00322             throw()
00323         {
00324             return (_ppForward ? _ppForward[iLevel] : NULL);
00325         }
00326 
00327         void forward( uint16_t iLevel, _Node* pNode )
00328             throw()
00329         {
00330             _ppForward[iLevel] = pNode;
00331         }
00332 
00333         K& key()
00334             throw()
00335         {
00336             return _Key;
00337         }
00338 
00339         const K& key() const
00340             throw()
00341         {
00342             return _Key;
00343         }
00344 
00345         void key( const K& rKey )
00346             throw()
00347         {
00348             _Key = rKey;
00349         }
00350 
00351         V& value()
00352             throw()
00353         {
00354             return _Value;
00355         }
00356 
00357         const V& value() const
00358             throw()
00359         {
00360             return _Value;
00361         }
00362 
00363         void value( const V& rValue )
00364             throw()
00365         {
00366             _Value = rValue;
00367         }
00368 
00369     private:
00370 
00371         _Node** _ppForward;
00372         K       _Key;
00373         V       _Value;
00374     };
00375 
00376 public:
00377 
00383     class Iterator : virtual public DWFCoreMemory
00384                    , public DWFKVIterator<K,V>
00385     {
00386     
00387     public:
00388 
00394         Iterator()
00395             throw()
00396             : _pNodeIterator( NULL )
00397             , _pCurrent( NULL )
00398         {;}      
00399 
00405         Iterator( typename _Node::_Iterator* pNodeIterator )
00406             throw()
00407             : _pNodeIterator( pNodeIterator )
00408             , _pCurrent( NULL )
00409         {;}      
00410 
00416         virtual ~Iterator()
00417             throw()
00418         {
00419             if (_pNodeIterator)
00420             {
00421                 DWFCORE_FREE_OBJECT( _pNodeIterator );
00422             }
00423         }
00424 
00425         virtual void reset()
00426             throw()
00427         {
00428             _pCurrent = NULL;
00429 
00430             if (_pNodeIterator)
00431             {
00432                 _pNodeIterator->reset();
00433             }
00434         }
00435 
00436         virtual bool valid()
00437             throw()
00438         {
00439             return (_pNodeIterator ? _pNodeIterator->valid() : false);
00440         }
00441 
00442         virtual bool next()
00443             throw()
00444         {
00445             _pCurrent = NULL;
00446 
00447             if (_pNodeIterator)
00448             {
00449                 return _pNodeIterator->next();
00450             }
00451             else
00452             {
00453                 return false;
00454             }
00455         }
00456         
00457         virtual K& key()
00458             throw( DWFException )
00459         {
00460             if (_pCurrent == NULL)
00461             {
00462                 if (_pNodeIterator)
00463                 {
00464                     _pCurrent = _pNodeIterator->get();
00465                 }
00466             }
00467             
00468             if (_pCurrent)
00469             {
00470                 return _pCurrent->key();
00471             }
00472             else
00473             {
00474                 _DWFCORE_THROW( DWFIllegalStateException, /*NOXLATE*/L"Cannot get key from iterator" );
00475             }
00476         }
00477 
00478         virtual V& value()
00479             throw( DWFException )
00480         {
00481             if (_pCurrent == NULL)
00482             {
00483                 if (_pNodeIterator)
00484                 {
00485                     _pCurrent = _pNodeIterator->get();
00486                 }
00487             }
00488             
00489             if (_pCurrent)
00490             {
00491                 return _pCurrent->value();
00492             }
00493             else
00494             {
00495                 _DWFCORE_THROW( DWFIllegalStateException, /*NOXLATE*/L"Cannot get value from iterator" );
00496             }
00497         }
00498 
00499     private:
00500 
00501         typename _Node::_Iterator*  _pNodeIterator;
00502         _Node*                      _pCurrent;
00503     };
00504 
00510     class ConstIterator : virtual public DWFCoreMemory
00511                         , public DWFKVConstIterator<K,V>
00512     {
00513     
00514     public:
00515 
00521         ConstIterator()
00522             throw()
00523             : _pNodeIterator( NULL )
00524             , _pCurrent( NULL )
00525         {;}      
00526 
00532         ConstIterator( typename _Node::_ConstIterator* pNodeIterator )
00533             throw()
00534             : _pNodeIterator( pNodeIterator )
00535             , _pCurrent( NULL )
00536         {;}      
00537 
00543         virtual ~ConstIterator()
00544             throw()
00545         {
00546             if (_pNodeIterator)
00547             {
00548                 DWFCORE_FREE_OBJECT( _pNodeIterator );
00549             }
00550         }
00551 
00552         virtual void reset()
00553             throw()
00554         {
00555             _pCurrent = NULL;
00556 
00557             if (_pNodeIterator)
00558             {
00559                 _pNodeIterator->reset();
00560             }
00561         }
00562 
00563         virtual bool valid()
00564             throw()
00565         {
00566             return (_pNodeIterator ? _pNodeIterator->valid() : false);
00567         }
00568 
00569         virtual bool next()
00570             throw()
00571         {
00572             _pCurrent = NULL;
00573 
00574             if (_pNodeIterator)
00575             {
00576                 return _pNodeIterator->next();
00577             }
00578             else
00579             {
00580                 return false;
00581             }
00582         }
00583         
00584         virtual const K& key()
00585             throw( DWFException )
00586         {
00587             if (_pCurrent == NULL)
00588             {
00589                 if (_pNodeIterator)
00590                 {
00591                     _pCurrent = _pNodeIterator->get();
00592                 }
00593             }
00594             
00595             if (_pCurrent)
00596             {
00597                 return _pCurrent->key();
00598             }
00599             else
00600             {
00601                 _DWFCORE_THROW( DWFIllegalStateException, /*NOXLATE*/L"Cannot get key from iterator" );
00602             }
00603         }
00604 
00605         virtual const V& value()
00606             throw( DWFException )
00607         {
00608             if (_pCurrent == NULL)
00609             {
00610                 if (_pNodeIterator)
00611                 {
00612                     _pCurrent = _pNodeIterator->get();
00613                 }
00614             }
00615             
00616             if (_pCurrent)
00617             {
00618                 return _pCurrent->value();
00619             }
00620             else
00621             {
00622                 _DWFCORE_THROW( DWFIllegalStateException, /*NOXLATE*/L"Cannot get value from iterator" );
00623             }
00624         }
00625 
00626     private:
00627 
00628         typename _Node::_ConstIterator*  _pNodeIterator;
00629         _Node const*                     _pCurrent;
00630     };
00631 
00632 public:
00633 
00639     virtual void clear()
00640         throw( DWFMemoryException )
00641     {
00642         _Node* pNext = NULL;
00643         typename _Node::_Iterator iNode( _pHeader->forward(0) );
00644 
00645         while (iNode.valid())
00646         {
00647             pNext = iNode.get();
00648             iNode.next();
00649 
00650             DWFCORE_FREE_OBJECT( pNext );
00651         }
00652 
00653         DWFCORE_FREE_OBJECT( _pHeader );
00654 
00655         //
00656         // Reset the maximum level and the initial maximum height.
00657         //
00658         _nMaxLevel  = 0;
00659         _nMaxHeight = DWFCORE_SKIPLIST_INITIAL_HEIGHT;
00660         
00661         //
00662         // Reset the element count to 0.
00663         //
00664         _nCount = 0;
00665 
00666         //
00667         // rebuild the header node
00668         //
00669         _pHeader = DWFCORE_ALLOC_OBJECT( _Node(DWFCORE_SKIPLIST_MAX_NODE_LEVEL) );
00670         if (_pHeader == NULL)
00671         {
00672             _DWFCORE_THROW( DWFMemoryException, /*NOXLATE*/L"Failed to allocate header node" );
00673         }
00674     }
00675 
00682     virtual size_t size() const
00683         throw()
00684     {
00685         return _nCount;
00686     }
00687 
00696     virtual Iterator* iterator()
00697         throw()
00698     {
00699         return DWFCORE_ALLOC_OBJECT(Iterator(DWFCORE_ALLOC_OBJECT(typename _Node::_Iterator(_pHeader->forward(0)))));
00700     }
00701 
00711     virtual ConstIterator* constIterator() const
00712         throw()
00713     {
00714         return DWFCORE_ALLOC_OBJECT(ConstIterator(DWFCORE_ALLOC_OBJECT(typename _Node::_ConstIterator(_pHeader->forward(0)))));
00715     }
00716 
00726     virtual Iterator* iterator( const K& rKey )
00727         throw()
00728     {
00729         return DWFCORE_ALLOC_OBJECT(Iterator(DWFCORE_ALLOC_OBJECT(typename _Node::_Iterator(_search(rKey)))));
00730     }
00731 
00742     virtual ConstIterator* constIterator( const K& rKey ) const
00743         throw()
00744     {
00745         return DWFCORE_ALLOC_OBJECT(ConstIterator(DWFCORE_ALLOC_OBJECT(typename _Node::_ConstIterator(_search(rKey)))));
00746     }
00747 
00755     virtual V* find( const K& rKey ) const
00756         throw()
00757     {    
00758         _Node* pSearch = _search( rKey );
00759           
00760             //
00761             // If the node was found then return the value. 
00762             //
00763         if (pSearch)
00764         {
00765             return &(pSearch->value());
00766         }
00767         else
00768         {
00769             return NULL;
00770         }
00771     }
00772 
00780     virtual K* key( uint64_t iPos )
00781         throw( DWFException )
00782     {
00783         if (iPos >= _nCount)
00784         {
00785             _DWFCORE_THROW( DWFOverflowException, /*NOXLATE*/L"Index exceeds list size" );
00786         }
00787 
00788         _Node* pNode = _pHeader->forward( 0 );
00789 
00790         for (; iPos > 0; iPos--)
00791         {
00792             pNode = pNode->forward( 0 );
00793         }
00794 
00795         return &(pNode->key());
00796     }
00797 
00805     virtual V* value( uint64_t iPos )
00806         throw( DWFException )
00807     {
00808         if (iPos >= _nCount)
00809         {
00810             _DWFCORE_THROW( DWFOverflowException, /*NOXLATE*/L"Index exceeds list size" );
00811         }
00812 
00813         _Node* pNode = _pHeader->forward( 0 );
00814 
00815         for (; iPos > 0; iPos--)
00816         {
00817             pNode = pNode->forward( 0 );
00818         }
00819 
00820         return &(pNode->value());
00821     }
00822 
00830     virtual bool erase( const K& rKey )
00831         throw()
00832     {
00833         //
00834         // refresh _ppUpdate
00835         //
00836         DWFCORE_ZERO_MEMORY( _ppUpdate, sizeof(_Node*) * (DWFCORE_SKIPLIST_MAX_NODE_LEVEL + 1) );
00837 
00838         _Node*  pCurrentNode = _pHeader;
00839         _Node*  pAlreadyChecked = NULL;
00840             
00841         //
00842         // Locate key of value immediately to the left of the key in rank.  During
00843         // the loop skip first using the largest steps possible and then proceed
00844         // with successively smaller steps (levels).   At each level maintain the
00845         // last visited node of that level (used for updating later).
00846         //
00847         int16_t iLevel = _nMaxLevel;
00848         for (; iLevel >= 0; iLevel--)
00849         {
00850             while ((pCurrentNode->forward(iLevel) != NULL) && 
00851                    (pCurrentNode->forward(iLevel) != pAlreadyChecked) &&
00852                    (_tLessThan(pCurrentNode->forward(iLevel)->key(), rKey)))
00853             {
00854                 pCurrentNode = pCurrentNode->forward( iLevel );
00855             }
00856                 
00857             pAlreadyChecked = pCurrentNode->forward( iLevel );
00858             _ppUpdate[iLevel] = pCurrentNode;
00859         }
00860         
00861         //
00862         // Get the next node.
00863         //
00864         pCurrentNode = pCurrentNode->forward( 0 );
00865           
00866 
00867             //
00868             // If the current key is equal to that supplied then just update the value
00869             // and we are done.
00870             //
00871         if ((pCurrentNode != NULL) && _tEquals(pCurrentNode->key(), rKey))
00872         {
00873                 //
00874                 // Iterate through all previously last-visited nodes of each level and update
00875                 // their forward references to be the same of the deleted nodes level-equivalent
00876                 // forward references.
00877                 //
00878             for (iLevel = 0; iLevel <= _nMaxLevel; iLevel++)
00879             {
00880                 if (_ppUpdate[iLevel]->forward(iLevel) != pCurrentNode)
00881                 {
00882                     break;
00883                 }
00884                     
00885                 _ppUpdate[iLevel]->forward( iLevel, pCurrentNode->forward(iLevel) );
00886             }
00887 
00888                 //
00889                 // Readjust the maximum level in the skip-list if necessary by iterating through the
00890                 // header's forward references and checking for null references at the highest levels back.
00891                 //
00892             while((_nMaxLevel>0) && (_pHeader->forward(_nMaxLevel) == NULL))
00893             {
00894                 _nMaxLevel--;
00895             }
00896         
00897             _nCount--;
00898         
00899             DWFCORE_FREE_OBJECT( pCurrentNode );
00900 
00901             return true;
00902         } 
00903         else
00904         {
00905             return false;
00906         }
00907     }
00908 
00920     virtual bool insert( const K& rKey, const V& rValue, bool bReplace = true )
00921         throw( DWFException )
00922     {
00923         //
00924         // refresh _ppUpdate
00925         //
00926         DWFCORE_ZERO_MEMORY( _ppUpdate, sizeof(_Node*) * (DWFCORE_SKIPLIST_MAX_NODE_LEVEL + 1) );
00927 
00928         _Node*  pCurrentNode = _pHeader;
00929         _Node*  pAlreadyChecked = NULL;
00930             
00931         //
00932         // Locate key of value immediately to the left of the key in rank.  During
00933         // the loop skip first using the largest steps possible and then proceed
00934         // with successively smaller steps (levels).   At each level maintain the
00935         // last visited node of that level (used for updating later).
00936         //
00937         int16_t iLevel = _nMaxLevel;
00938         for (; iLevel >= 0; iLevel--)
00939         {
00940             while ((pCurrentNode->forward(iLevel) != NULL) && 
00941                    (pCurrentNode->forward(iLevel) != pAlreadyChecked) &&
00942                    (_tLessThan(pCurrentNode->forward(iLevel)->key(), rKey)))
00943             {
00944                 pCurrentNode = pCurrentNode->forward( iLevel );
00945             }
00946                 
00947             pAlreadyChecked = pCurrentNode->forward( iLevel );
00948             _ppUpdate[iLevel] = pCurrentNode;
00949         }
00950             
00951         //
00952         // Get the next node.
00953         //
00954         pCurrentNode = pCurrentNode->forward( 0 );
00955           
00956             //
00957             // If the current key is equal to that supplied then just update the value
00958             // and we are done.
00959             //
00960         if ((pCurrentNode != NULL) && (_tEquals(pCurrentNode->key(), rKey)))
00961         {                  
00962             if (bReplace)
00963             {
00964                 pCurrentNode->key( rKey );
00965                 pCurrentNode->value( rValue );
00966             }
00967 
00968             return false;
00969         }
00970         else
00971         {
00972             //
00973             // Generate a random level (height) for the new node.
00974             //
00975             uint16_t nNewLevel = _random();
00976               
00977                 //
00978                 // Update the maximum level height if this level is now larger.  (Could only be one greater!)
00979                 //
00980             if (nNewLevel >= _nMaxHeight)
00981             {
00982                 _nMaxHeight = nNewLevel + 1;
00983             }
00984                 
00985                 //
00986                 // If this level is the largest level so far selected in the skip-list then extend the
00987                 // list of maintain "update" pointers (of previously visited nodes of each level) for the
00988                 // intermediate levels between the previous maximum and the new maximum.
00989                 //
00990                 // Also checks to see that the absolute maximum has been reached and restricts the height increase.
00991                 //
00992             if (nNewLevel > _nMaxLevel)
00993             {
00994                 for(iLevel = _nMaxLevel + 1; iLevel <= nNewLevel; iLevel++)
00995                 {
00996                     _ppUpdate[iLevel] = _pHeader;
00997                 }
00998                  
00999                 //
01000                 // Update the skip-list maximum level from here on.
01001                 //
01002                 _nMaxLevel = nNewLevel;
01003             }
01004                 
01005             //
01006             // Create a new node.
01007             //
01008             pCurrentNode = DWFCORE_ALLOC_OBJECT( _Node(nNewLevel, rKey, rValue) );
01009 
01010             if (pCurrentNode == NULL)
01011             {
01012                 _DWFCORE_THROW( DWFMemoryException, /*NOXLATE*/L"Failed to allocate node" );
01013             }
01014               
01015                 //
01016                 // Update all forward references of previous skip-list nodes to reference the new value and 
01017                 // set the forward references of the new node to those of the previous update nodes at each level.
01018                 //
01019             for (iLevel = 0; iLevel <= nNewLevel; iLevel++)
01020             {
01021                 pCurrentNode->forward( iLevel, _ppUpdate[iLevel]->forward(iLevel) );
01022                 _ppUpdate[iLevel]->forward( iLevel, pCurrentNode );
01023             }                            
01024                 
01025             _nCount++;
01026 
01027             return true;
01028         }
01029     }
01030 
01031 private:
01032 
01033     //
01034     //
01035     //
01036     _Node* _search( const K& rKey ) const
01037         throw()
01038     {    
01039         _Node*  pCurrentNode = _pHeader;
01040         _Node*  pAlreadyChecked = NULL;
01041 
01042         //
01043         // Locate key of value immediately to the left of the key in rank.  During
01044         // the loop skip first using the largest steps possible and then proceed
01045         // with successively smaller steps (levels).   At each level maintain the
01046         // last visited node of that level (used for updating later).
01047         //
01048         int16_t iLevel = _nMaxLevel;
01049         for (; iLevel >= 0; iLevel--)
01050         {
01051             while ((pCurrentNode->forward(iLevel) != NULL) && 
01052                    (pCurrentNode->forward(iLevel) != pAlreadyChecked) &&
01053                    (_tLessThan(pCurrentNode->forward(iLevel)->key(), rKey)))
01054             {
01055                 pCurrentNode = pCurrentNode->forward( iLevel );
01056             }
01057                 
01058             pAlreadyChecked = pCurrentNode->forward( iLevel );
01059         }
01060 
01061         //
01062         // Get the next node.
01063         //
01064         pCurrentNode = pCurrentNode->forward( 0 );
01065           
01066             //
01067             // If the node was found then return the value. 
01068             //
01069         if ((pCurrentNode != NULL) && (_tEquals(pCurrentNode->key(), rKey)))
01070         {
01071             return pCurrentNode;
01072         }
01073         else
01074         {
01075             return NULL;
01076         }
01077     }
01078 
01079     uint16_t _random()
01080         throw()
01081     {
01082         uint16_t nLevel = 1;
01083         static bool bSeed = true;
01084 
01085         if (bSeed)
01086         {
01087             ::srand( DWFTimer::Tick32() );
01088             bSeed = false;
01089         }
01090 
01091 
01092         while ((::rand() < (RAND_MAX * DWFCORE_SKIPLIST_PROBABILITY_DISTRIB)) &&
01093                (nLevel <= _nMaxHeight) &&
01094                (nLevel < DWFCORE_SKIPLIST_MAX_NODE_LEVEL))
01095         {
01096             nLevel++;
01097         }
01098 
01099         return nLevel;
01100     }
01101 
01102 
01103 private:
01104 
01105         //
01106         // First node in the list ... does not represent a key.
01107         //
01108     _Node*      _pHeader;   
01109 
01110         //
01111         // Update node array used in _insert and _delete
01112         // Keep it here and use the maximum node level size
01113         // to eliminate allocations
01114         //
01115     _Node*      _ppUpdate[DWFCORE_SKIPLIST_MAX_NODE_LEVEL + 1];
01116 
01117         //
01118         // Current maximum height of a node allowed.
01119         //
01120     uint16_t    _nMaxHeight;
01121 
01122         //
01123         // Current maximum level used in any node.
01124         //
01125     uint16_t    _nMaxLevel;
01126 
01127         //
01128         // Current count of items in the list.
01129         //
01130     uint32_t    _nCount;
01131 
01132     //
01133     // Comparators
01134     //
01135     E           _tEquals;
01136     L           _tLessThan;
01137 
01138 private:
01139 
01140     DWFSkipList( const DWFSkipList& );
01141     DWFSkipList& operator=( const DWFSkipList& );
01142 };
01143 
01154 template<class V>
01155 class DWFCharKeySkipList : public DWFSkipList<const char*, V, tDWFCharCompareEqual, tDWFCharCompareLess>
01156                          , virtual public DWFCoreMemory
01157 {
01158 public:
01159 
01165     DWFCharKeySkipList() throw() {;}
01166 
01172     virtual ~DWFCharKeySkipList() throw() {;}
01173 
01174 private:
01175 
01176     //
01177     // Not Implemented
01178     //
01179     DWFCharKeySkipList( const DWFCharKeySkipList& );
01180     DWFCharKeySkipList& operator=( const DWFCharKeySkipList& );
01181 };
01182 
01217 template<class V>
01218 class DWFWCharKeySkipList : public DWFSkipList<const wchar_t*, V, tDWFWCharCompareEqual, tDWFWCharCompareLess>
01219                           , virtual public DWFCoreMemory
01220 {
01221 public:
01222 
01228     DWFWCharKeySkipList() throw() {;}
01229 
01235     virtual ~DWFWCharKeySkipList() throw() {;}
01236 
01237 private:
01238 
01239     //
01240     // Not Implemented
01241     //
01242     DWFWCharKeySkipList( const DWFWCharKeySkipList& );
01243     DWFWCharKeySkipList& operator=( const DWFWCharKeySkipList& );
01244 };
01245 
01253 template<class V>
01254 class DWFStringKeySkipList : public DWFSkipList<DWFString, V, tDWFCompareEqual<DWFString>, tDWFCompareLess<DWFString>, tDWFStringDefinedEmpty>
01255                            , virtual public DWFCoreMemory
01256 {
01257 public:
01258 
01264     DWFStringKeySkipList() throw() {;}
01265 
01271     virtual ~DWFStringKeySkipList() throw() {;}
01272 
01273 private:
01274 
01275     //
01276     // Not Implemented
01277     //
01278     DWFStringKeySkipList( const DWFStringKeySkipList& );
01279     DWFStringKeySkipList& operator=( const DWFStringKeySkipList& );
01280 };
01281 
01282 
01293 template<class T, class E = tDWFCompareEqual<T>, class L = tDWFCompareLess<T>, class Z = tDWFDefinedEmpty<T> >
01294 class DWFSortedList : virtual public DWFCoreMemory
01295 {
01296 
01297 private:
01298 
01299     typedef typename DWFSkipList<T, T, E, L, Z>::Iterator tListIterator;
01300     typedef typename DWFSkipList<T, T, E, L, Z>::ConstIterator tListConstIterator;
01301 
01302 public:
01303 
01309     class Iterator : virtual public DWFCoreMemory
01310                    , public DWFIterator<T>
01311     {
01312         
01313     public:
01314 
01321         Iterator( tListIterator* pIterator )
01322             throw()
01323             : _pIterator( pIterator )
01324         {;}
01325 
01331         virtual ~Iterator()
01332             throw()
01333         {
01334             DWFCORE_FREE_OBJECT( _pIterator );
01335         }
01336 
01337         virtual void reset()
01338             throw()
01339         {
01340             _pIterator->reset();
01341         }
01342 
01343         virtual bool valid()
01344             throw()
01345         {
01346             return _pIterator->valid();
01347         }
01348 
01349         virtual bool next()
01350             throw()
01351         {
01352             return _pIterator->next();
01353         }
01354             
01355         virtual T& get()
01356             throw()
01357         {
01358             return _pIterator->key();
01359         }
01360 
01361     private:
01362 
01363         tListIterator* _pIterator;
01364     };
01365 
01371     class ConstIterator : virtual public DWFCoreMemory
01372                         , public DWFConstIterator<T>
01373     {
01374         
01375     public:
01376 
01383         ConstIterator( tListConstIterator* pConstIterator )
01384             throw()
01385             : _pConstIterator( pConstIterator )
01386         {;}
01387 
01393         virtual ~ConstIterator()
01394             throw()
01395         {
01396             DWFCORE_FREE_OBJECT( _pConstIterator );
01397         }
01398 
01399         virtual void reset()
01400             throw()
01401         {
01402             _pConstIterator->reset();
01403         }
01404 
01405         virtual bool valid() const
01406             throw()
01407         {
01408             return _pConstIterator->valid();
01409         }
01410 
01411         virtual bool next()
01412             throw()
01413         {
01414             return _pConstIterator->next();
01415         }
01416             
01417         virtual const T& get() const
01418             throw( DWFException )
01419         {
01420             return _pConstIterator->key();
01421         }
01422 
01423     private:
01424 
01425         tListConstIterator* _pConstIterator;
01426     };
01427 
01428 public:
01429 
01435     DWFSortedList()
01436         throw()
01437     {;}
01438 
01444     virtual ~DWFSortedList()
01445         throw()
01446     {;}
01447 
01451     virtual void clear()
01452         throw()
01453     {
01454         _oList.clear();
01455     }
01456 
01460     virtual size_t size() const
01461         throw()
01462     {
01463         return _oList.size();
01464     }
01465     
01469     virtual Iterator* iterator()
01470         throw()
01471     {
01472         return DWFCORE_ALLOC_OBJECT( Iterator(_oList.iterator()) );
01473     }
01474 
01478     virtual ConstIterator* constIterator() const
01479         throw()
01480     {
01481         return DWFCORE_ALLOC_OBJECT( ConstIterator(_oList.constIterator()) );
01482     }
01483 
01493     virtual Iterator* iterator( const T& rT )
01494         throw()
01495     {
01496         return DWFCORE_ALLOC_OBJECT( Iterator(_oList.iterator(rT)) );
01497     }
01498 
01509     virtual ConstIterator* constIterator( const T& rT ) const
01510         throw()
01511     {
01512         return DWFCORE_ALLOC_OBJECT( ConstIterator(_oList.constIterator(rT)) );
01513     }
01514 
01522     virtual bool exists( const T& rT ) const
01523         throw()
01524     {    
01525         return (_oList.find(rT) != NULL);
01526     }
01527 
01535     virtual bool erase( const T& rT )
01536         throw()
01537     {
01538         return _oList.erase( rT );
01539     }
01540  
01551     virtual bool insert( const T& rT, bool bReplace = true )
01552         throw( DWFException )
01553     {
01554         return _oList.insert( rT, rT, bReplace );
01555     }
01556 
01557 private:
01558 
01559     DWFSkipList<T, T>   _oList;
01560 
01561 private:
01562 
01563     //
01564     // Not Implemented
01565     //
01566     DWFSortedList( const DWFSortedList& );
01567     DWFSortedList& operator=( const DWFSortedList& );
01568 };
01569 
01573 
01574 
01590 template< class T, class H = tDWFFNV1A32HashKernel<const char> >
01591 class DWFCharKeyHashList    : virtual public DWFCoreMemory
01592 {
01593 
01594 private:
01595 
01596     typedef typename DWFSkipList<uint32_t, T>::Iterator tListIterator;
01597     typedef typename DWFSkipList<uint32_t, T>::ConstIterator tListConstIterator;
01598 
01599 public:
01600 
01606     class Iterator : virtual public DWFCoreMemory
01607                    , public DWFIterator<T>
01608     {
01609         
01610     public:
01611 
01618         Iterator( tListIterator* pIterator )
01619             throw()
01620             : _pIterator( pIterator )
01621         {;}
01622 
01628         virtual ~Iterator()
01629             throw()
01630         {
01631             DWFCORE_FREE_OBJECT( _pIterator );
01632         }
01633 
01634         virtual void reset()
01635             throw()
01636         {
01637             _pIterator->reset();
01638         }
01639 
01640         virtual bool valid()
01641             throw()
01642         {
01643             return _pIterator->valid();
01644         }
01645 
01646         virtual bool next()
01647             throw()
01648         {
01649             return _pIterator->next();
01650         }
01651             
01652         virtual T& get()
01653             throw()
01654         {
01655             return _pIterator->value();
01656         }
01657 
01658     private:
01659 
01660         tListIterator* _pIterator;
01661     };    
01662 
01668     class ConstIterator : virtual public DWFCoreMemory
01669                         , public DWFConstIterator<T>
01670     {
01671         
01672     public:
01673 
01680         ConstIterator( tListConstIterator* pConstIterator )
01681             throw()
01682             : _pConstIterator( pConstIterator )
01683         {;}
01684 
01690         virtual ~ConstIterator()
01691             throw()
01692         {
01693             DWFCORE_FREE_OBJECT( _pConstIterator );
01694         }
01695 
01696         virtual void reset()
01697             throw()
01698         {
01699             _pConstIterator->reset();
01700         }
01701 
01702         virtual bool valid() const
01703             throw()
01704         {
01705             return _pConstIterator->valid();
01706         }
01707 
01708         virtual bool next()
01709             throw()
01710         {
01711             return _pConstIterator->next();
01712         }
01713             
01714         virtual const T& get() const
01715             throw( DWFException )
01716         {
01717             return _pConstIterator->value();
01718         }
01719 
01720     private:
01721 
01722         tListConstIterator* _pConstIterator;
01723     };    
01724 
01725 public:
01726 
01732     DWFCharKeyHashList()
01733         throw()
01734         : _tHash()
01735     {;}
01736 
01742     virtual ~DWFCharKeyHashList()
01743         throw()
01744     {;}
01745 
01749     virtual void clear()
01750         throw()
01751     {
01752         //
01753         // clear base
01754         //
01755         _oList.clear();
01756     }
01757 
01761     virtual size_t size() const
01762         throw()
01763     {
01764         return _oList.size();
01765     }
01766 
01770     virtual Iterator* iterator()
01771         throw()
01772     {
01773         return DWFCORE_ALLOC_OBJECT( Iterator(_oList.iterator()) );
01774     }
01775 
01779     virtual ConstIterator* constIterator() const
01780         throw()
01781     {
01782         return DWFCORE_ALLOC_OBJECT( ConstIterator(_oList.constIterator()) );
01783     }
01784 
01788     virtual Iterator* iterator( const char*& rKey )
01789         throw()
01790     {
01791         return DWFCORE_ALLOC_OBJECT( Iterator(_oList.iterator(_tHash(rKey))) );
01792     }
01793 
01797     virtual ConstIterator* constIterator( const char*& rKey ) const
01798         throw()
01799     {
01800         return DWFCORE_ALLOC_OBJECT( ConstIterator(_oList.constIterator(_tHash(rKey))) );
01801     }
01802 
01806     virtual T* find( const char*& rKey ) const
01807         throw()
01808     {
01809         return _oList.find( _tHash(rKey) );
01810     }
01811 
01815     virtual bool erase( const char*& rKey )
01816         throw()
01817     {
01818         return _oList.erase( _tHash(rKey) );
01819     }
01820 
01824     virtual bool insert( const char*& rKey, const T& rValue, bool bReplace = true )
01825         throw( DWFException )
01826     {
01827         return _oList.insert( _tHash(rKey), rValue, bReplace );
01828     }
01829 
01830 private:
01831 
01832     H                        _tHash;
01833     DWFSkipList<uint32_t, T> _oList;
01834 
01835 private:
01836 
01837     //
01838     // Not Implemented
01839     //
01840     DWFCharKeyHashList( const DWFCharKeyHashList& );
01841     DWFCharKeyHashList& operator=( const DWFCharKeyHashList& );
01842 };
01843 
01847 
01863 template< class T, class H = tDWFFNV1A32HashKernel<const wchar_t> >
01864 class DWFWCharKeyHashList   : virtual public DWFCoreMemory
01865 {
01866 
01867 private:
01868 
01869     typedef typename DWFSkipList<uint32_t, T>::Iterator tListIterator;
01870     typedef typename DWFSkipList<uint32_t, T>::ConstIterator tListConstIterator;
01871 
01872 public:
01873 
01879     class Iterator : virtual public DWFCoreMemory
01880                    , public DWFIterator<T>
01881     {
01882         
01883     public:
01884 
01891         Iterator( tListIterator* pIterator )
01892             throw()
01893             : _pIterator( pIterator )
01894         {;}
01895 
01901         virtual ~Iterator()
01902             throw()
01903         {
01904             DWFCORE_FREE_OBJECT( _pIterator );
01905         }
01906 
01907         virtual void reset()
01908             throw()
01909         {
01910             _pIterator->reset();
01911         }
01912 
01913         virtual bool valid()
01914             throw()
01915         {
01916             return _pIterator->valid();
01917         }
01918 
01919         virtual bool next()
01920             throw()
01921         {
01922             return _pIterator->next();
01923         }
01924             
01925         virtual T& get()
01926             throw()
01927         {
01928             return _pIterator->value();
01929         }
01930 
01931     private:
01932 
01933         tListIterator* _pIterator;
01934     };    
01935 
01941     class ConstIterator : virtual public DWFCoreMemory
01942                         , public DWFConstIterator<T>
01943     {
01944         
01945     public:
01946 
01953         ConstIterator( tListConstIterator* pConstIterator )
01954             throw()
01955             : _pConstIterator( pConstIterator )
01956         {;}
01957 
01963         virtual ~ConstIterator()
01964             throw()
01965         {
01966             DWFCORE_FREE_OBJECT( _pConstIterator );
01967         }
01968 
01969         virtual void reset()
01970             throw()
01971         {
01972             _pConstIterator->reset();
01973         }
01974 
01975         virtual bool valid() const
01976             throw()
01977         {
01978             return _pConstIterator->valid();
01979         }
01980 
01981         virtual bool next()
01982             throw()
01983         {
01984             return _pConstIterator->next();
01985         }
01986             
01987         virtual const T& get() const
01988             throw( DWFException )
01989         {
01990             return _pConstIterator->value();
01991         }
01992 
01993     private:
01994 
01995         tListConstIterator* _pConstIterator;
01996     };    
01997 
01998 public:
01999 
02005     DWFWCharKeyHashList()
02006         throw()
02007     {;}
02008 
02014     virtual ~DWFWCharKeyHashList()
02015         throw()
02016     {;}
02017 
02021     virtual void clear()
02022         throw()
02023     {
02024         //
02025         // clear base
02026         //
02027         _oList.clear();
02028     }
02029 
02033     virtual size_t size() const
02034         throw()
02035     {
02036         return _oList.size();
02037     }
02038 
02042     virtual Iterator* iterator()
02043         throw()
02044     {
02045         return DWFCORE_ALLOC_OBJECT( Iterator(_oList.iterator()) );
02046     }
02047 
02051     virtual ConstIterator* constIterator() const
02052         throw()
02053     {
02054         return DWFCORE_ALLOC_OBJECT( ConstIterator(_oList.constIterator()) );
02055     }
02056 
02060     virtual Iterator* iterator( const wchar_t*& rKey )
02061         throw()
02062     {
02063         return DWFCORE_ALLOC_OBJECT( Iterator(_oList.iterator(_tHash(rKey))) );
02064     }
02065 
02069     virtual ConstIterator* constIterator( const wchar_t*& rKey ) const
02070         throw()
02071     {
02072         return DWFCORE_ALLOC_OBJECT( ConstIterator(_oList.constIterator(_tHash(rKey))) );
02073     }
02074 
02078     virtual T* find( const wchar_t*& rKey ) const
02079         throw()
02080     {
02081         return _oList.find( _tHash(rKey) );
02082     }
02083 
02087     virtual bool erase( const wchar_t*& rKey )
02088         throw()
02089     {
02090         return _oList.erase( _tHash(rKey) );
02091     }
02092 
02096     virtual bool insert( const wchar_t*& rKey, const T& rValue, bool bReplace = true )
02097         throw( DWFException )
02098     {
02099         return _oList.insert( _tHash(rKey), rValue, bReplace );
02100     }
02101 
02102 private:
02103 
02104     H                        _tHash;
02105     DWFSkipList<uint32_t, T> _oList;
02106 
02107 private:
02108 
02109     //
02110     // Not Implemented
02111     //
02112     DWFWCharKeyHashList( const DWFWCharKeyHashList& );
02113     DWFWCharKeyHashList& operator=( const DWFWCharKeyHashList& );
02114 };
02115 
02116 
02133 template<class PK, class SK, class V, 
02134          class PE = tDWFCompareEqual<PK>, class SE = tDWFCompareEqual<SK>, 
02135          class PL = tDWFCompareLess<PK>, class SL = tDWFCompareLess<SK>, 
02136          class PZ = tDWFDefinedEmpty<PK>, class SZ = tDWFDefinedEmpty<SK> >
02137 class DWFChainedSkipList    : virtual public DWFCoreMemory
02138 {
02139 
02140     typedef typename DWFSkipList<SK, V, SE, SL, SZ>::Iterator _tChainIterator;
02141     typedef typename DWFSkipList<SK, V, SE, SL, SZ>::ConstIterator _tChainConstIterator;
02142     typedef typename DWFSkipList<PK, DWFSkipList<SK, V, SE, SL, SZ>*, PE, PL, PZ>::Iterator _tListIterator;
02143     typedef typename DWFSkipList<PK, DWFSkipList<SK, V, SE, SL, SZ>*, PE, PL, PZ>::ConstIterator _tListConstIterator;
02144 
02145 public:
02146 
02152     class Iterator : public DWFSkipList<SK, V, SE, SL, SZ>::Iterator
02153                    , virtual public DWFCoreMemory
02154     {
02155         public:
02156 
02157             Iterator( _tChainIterator* piChain )
02158                 throw()
02159                 : _piList( NULL )
02160                 , _piChain( piChain )
02161             {;}
02162 
02163     //
02164     // The MSVC 7.0 pre-processor cannot resolve the difference
02165     // between  typedef typename _tChainIterator 
02166     // and      typedef typename _tListIterator
02167     // so this hack becomes necessary to prevent the constructor
02168     // appearing to be declared twice.
02169     //
02170 #if defined( _DWFCORE_WIN32_SYSTEM ) && ( _MSC_VER <= 1300 )
02171             Iterator( _tListIterator* piList, int )
02172 #else
02179             Iterator( _tListIterator* piList )
02180 #endif
02181                 throw()
02182                 : _piList( piList )
02183                 , _piChain( NULL )
02184             {
02185                 if (piList && (piList->valid()))
02186                 {
02187                     _piChain = piList->value()->iterator();
02188                 }
02189             }
02190 
02196             virtual ~Iterator()
02197                 throw()
02198             {
02199                 if (_piChain)
02200                 {
02201                     DWFCORE_FREE_OBJECT( _piChain );
02202                 }
02203                 if (_piList)
02204                 {
02205                     DWFCORE_FREE_OBJECT( _piList );
02206                 }
02207             }
02208 
02209             void reset()
02210                 throw()
02211             {
02212                     //
02213                     // always work on composite iterator first
02214                     //
02215                 if (_piList)
02216                 {
02217                     //
02218                     // reset
02219                     //
02220                     _piList->reset();
02221 
02222                         //
02223                         // free any intermediate chain iterator
02224                         //
02225                     if (_piChain)
02226                     {
02227                         DWFCORE_FREE_OBJECT( _piChain );
02228                         _piChain = NULL;
02229                     }
02230                 }
02231                     //
02232                     // we are only a chain iterator
02233                     //
02234                 else if (_piChain)
02235                 {
02236                     _piChain->reset();
02237                 }
02238             }
02239 
02240             bool valid()
02241                 throw()
02242             {
02243                     //
02244                     // always work on composite iterator first
02245                     //
02246                 if (_piList && _piList->valid())
02247                 {
02248                         //
02249                         // the intermediate chain iterator is not valid
02250                         // move on the the next one
02251                         //
02252                     if (_piChain && (_piChain->valid() == false))
02253                     {
02254                         DWFCORE_FREE_OBJECT( _piChain );
02255                         _piChain = NULL;
02256 
02257                             //
02258                             // get the next intermediate iterator
02259                             //
02260                         if (_piList->next())
02261                         {
02262                             _piChain = _piList->value()->iterator();
02263                         }
02264                     }
02265 
02266                     //
02267                     // if _piChain is NULL at this point, 
02268                     // there are no more chained iterators
02269                     //
02270                 }
02271 
02272                 return (_piChain ? _piChain->valid() : false);
02273             }
02274 
02275             bool next()
02276                 throw()
02277             {
02278                     //
02279                     // this pointer should always be accurate
02280                     //
02281                 if (_piChain)
02282                 {
02283                         //
02284                         // in this case, if next() is false,
02285                         // we need to try and get the next intermediate iterator
02286                         //
02287                     if (_piList && (_piChain->next() == false))
02288                     {
02289                         DWFCORE_FREE_OBJECT( _piChain );
02290                         _piChain = NULL;
02291 
02292                             //
02293                             // get the next intermediate iterator
02294                             //
02295                         if (_piList->next())
02296                         {
02297                             _piChain = _piList->value()->iterator();
02298                         }
02299                     }
02300 
02301                     if (_piChain)
02302                     {
02303                         return _piChain->valid();
02304                     }
02305                 }
02306 
02307                 return false;
02308             }
02309             
02310             SK& key()
02311                 throw( DWFException )
02312             {
02313                 if (_piChain)
02314                 {
02315                     return _piChain->key();
02316                 }
02317                 else
02318                 {
02319                     _DWFCORE_THROW( DWFDoesNotExistException, /*NOXLATE*/L"No more elements" );
02320                 }
02321             }
02322 
02323             V& value()
02324                 throw( DWFException )
02325             {
02326                 if (_piChain)
02327                 {
02328                     return _piChain->value();
02329                 }
02330                 else
02331                 {
02332                     _DWFCORE_THROW( DWFDoesNotExistException, /*NOXLATE*/L"No more elements" );
02333                 }
02334             }
02335 
02336         private:
02337 
02338             _tListIterator*     _piList;
02339             _tChainIterator*    _piChain;
02340         };
02341 
02347     class ConstIterator : public DWFSkipList<SK, V, SE, SL, SZ>::ConstIterator
02348                         , virtual public DWFCoreMemory
02349     {
02350         public:
02351 
02352             ConstIterator( _tChainConstIterator* piChain )
02353                 throw()
02354                 : _piList( NULL )
02355                 , _piChain( piChain )
02356             {;}
02357 
02358     //
02359     // The MSVC 7.0 pre-processor cannot resolve the difference
02360     // between  typedef typename _tChainConstIterator 
02361     // and      typedef typename _tListConstIterator
02362     // so this hack becomes necessary to prevent the constructor
02363     // appearing to be declared twice.
02364     //
02365 #if defined( _DWFCORE_WIN32_SYSTEM ) && ( _MSC_VER <= 1300 )
02366             ConstIterator( _tListConstIterator* piList, int )
02367 #else
02374             ConstIterator( _tListConstIterator* piList )
02375 #endif
02376                 throw()
02377                 : _piList( piList )
02378                 , _piChain( NULL )
02379             {
02380                 if (piList && (piList->valid()))
02381                 {
02382                     _piChain = piList->value()->constIterator();
02383                 }
02384             }
02385 
02391             virtual ~ConstIterator()
02392                 throw()
02393             {
02394                 if (_piChain)
02395                 {
02396                     DWFCORE_FREE_OBJECT( _piChain );
02397                 }
02398                 if (_piList)
02399                 {
02400                     DWFCORE_FREE_OBJECT( _piList );
02401                 }
02402             }
02403 
02404             void reset()
02405                 throw()
02406             {
02407                     //
02408                     // always work on composite iterator first
02409                     //
02410                 if (_piList)
02411                 {
02412                     //
02413                     // reset
02414                     //
02415                     _piList->reset();
02416 
02417                         //
02418                         // free any intermediate chain iterator
02419                         //
02420                     if (_piChain)
02421                     {
02422                         DWFCORE_FREE_OBJECT( _piChain );
02423                         _piChain = NULL;
02424                     }
02425                 }
02426                     //
02427                     // we are only a chain iterator
02428                     //
02429                 else if (_piChain)
02430                 {
02431                     _piChain->reset();
02432                 }
02433             }
02434 
02435             bool valid() const
02436                 throw()
02437             {
02438                     //
02439                     // always work on composite iterator first
02440                     //
02441                 if (_piList && _piList->valid())
02442                 {
02443                         //
02444                         // the intermediate chain iterator is not valid
02445                         // move on the the next one
02446                         //
02447                     if (_piChain && (_piChain->valid() == false))
02448                     {
02449                         DWFCORE_FREE_OBJECT( _piChain );
02450                         _piChain = NULL;
02451 
02452                             //
02453                             // get the next intermediate iterator
02454                             //
02455                         if (_piList->next())
02456                         {
02457                             _piChain = _piList->value()->constIterator();
02458                         }
02459                     }
02460 
02461                     //
02462                     // if _piChain is NULL at this point, 
02463                     // there are no more chained iterators
02464                     //
02465                 }
02466 
02467                 return (_piChain ? _piChain->valid() : false);
02468             }
02469 
02470             bool next()
02471                 throw()
02472             {
02473                     //
02474                     // this pointer should always be accurate
02475                     //
02476                 if (_piChain)
02477                 {
02478                         //
02479                         // in this case, if next() is false,
02480                         // we need to try and get the next intermediate iterator
02481                         //
02482                     if (_piList && (_piChain->next() == false))
02483                     {
02484                         DWFCORE_FREE_OBJECT( _piChain );
02485                         _piChain = NULL;
02486 
02487                             //
02488                             // get the next intermediate iterator
02489                             //
02490                         if (_piList->next())
02491                         {
02492                             _piChain = _piList->value()->constIterator();
02493                         }
02494                     }
02495 
02496                     if (_piChain)
02497                     {
02498                         return _piChain->valid();
02499                     }
02500                 }
02501 
02502                 return false;
02503             }
02504             
02505             const SK& key()
02506                 throw( DWFException )
02507             {
02508                 if (_piChain)
02509                 {
02510                     return _piChain->key();
02511                 }
02512                 else
02513                 {
02514                     _DWFCORE_THROW( DWFDoesNotExistException, /*NOXLATE*/L"No more elements" );
02515                 }
02516             }
02517 
02518             const V& value()
02519                 throw( DWFException )
02520             {
02521                 if (_piChain)
02522                 {
02523                     return _piChain->value();
02524                 }
02525                 else
02526                 {
02527                     _DWFCORE_THROW( DWFDoesNotExistException, /*NOXLATE*/L"No more elements" );
02528                 }
02529             }
02530 
02531         private:
02532 
02533             _tListConstIterator*     _piList;
02534             _tChainConstIterator*    _piChain;
02535         };
02536 public:
02537 
02543     DWFChainedSkipList()
02544         throw()
02545     {;}
02546 
02552     virtual ~DWFChainedSkipList()
02553         throw()
02554     {
02555         _tListIterator* piChain = _oChains.iterator();
02556 
02557         if (piChain)
02558         {
02559             for (;piChain->valid(); piChain->next())
02560             {
02561                 DWFCORE_FREE_OBJECT( piChain->value() );
02562             }
02563             
02564             DWFCORE_FREE_OBJECT( piChain );
02565         }
02566     }
02567 
02571     virtual void clear()
02572         throw()
02573     {
02574         _tListIterator* piChain = _oChains.iterator();
02575         if (piChain)
02576         {
02577             for (;piChain->valid(); piChain->next())
02578             {
02579                 piChain->value()->clear();
02580             }
02581             DWFCORE_FREE_OBJECT( piChain );
02582         }
02583         
02584         _oChains.clear();
02585     }
02586 
02594     virtual size_t size() const
02595         throw()
02596     {
02597         size_t nCount = 0;
02598         _tListConstIterator* piChain = _oChains.constIterator();
02599     
02600         if (piChain)
02601         {
02602             for (;piChain->valid(); piChain->next())
02603             {
02604                 nCount += piChain->value()->size();
02605             }
02606             DWFCORE_FREE_OBJECT( piChain );
02607         }
02608 
02609         return nCount;
02610     }
02611 
02618     virtual size_t size( const PK& rPKey ) const
02619         throw()
02620     {
02621         DWFSkipList<SK, V, SE, SL, SZ>** ppChain = _oChains.find( rPKey );
02622 
02623         return (ppChain ? (*ppChain)->size() : 0);
02624     }
02625 
02629     virtual Iterator* iterator()
02630         throw()
02631     {
02632         //
02633         // see above
02634         //
02635 #if defined( _DWFCORE_WIN32_SYSTEM ) && ( _MSC_VER <= 1300 )
02636         return DWFCORE_ALLOC_OBJECT( Iterator(_oChains.iterator(), 0) );
02637 #else
02638         return DWFCORE_ALLOC_OBJECT( Iterator(_oChains.iterator()) );
02639 #endif
02640     }
02641 
02645     virtual ConstIterator* constIterator() const
02646         throw()
02647     {
02648         //
02649         // see above
02650         //
02651 #if defined( _DWFCORE_WIN32_SYSTEM ) && ( _MSC_VER <= 1300 )
02652         return DWFCORE_ALLOC_OBJECT( ConstIterator(_oChains.constIterator(), 0) );
02653 #else
02654         return DWFCORE_ALLOC_OBJECT( ConstIterator(_oChains.constIterator()) );
02655 #endif
02656     }
02657 
02669     virtual Iterator* iterator( const PK& rPKey )
02670         throw()
02671     {
02672         DWFSkipList<SK, V, SE, SL, SZ>** ppChain = _oChains.find( rPKey );
02673 
02674         return (ppChain ? DWFCORE_ALLOC_OBJECT(Iterator((*ppChain)->iterator())) : NULL);
02675     }
02676 
02689     virtual ConstIterator* constIterator( const PK& rPKey ) const
02690         throw()
02691     {
02692         DWFSkipList<SK, V, SE, SL, SZ>** ppChain = _oChains.find( rPKey );
02693 
02694         return (ppChain ? DWFCORE_ALLOC_OBJECT(ConstIterator((*ppChain)->constIterator())) : NULL);
02695     }
02696 
02709     virtual Iterator* iterator( const PK& rPKey, const SK& rSKey )
02710         throw()
02711     {
02712         DWFSkipList<SK, V, SE, SL, SZ>** ppChain = _oChains.find( rPKey );
02713 
02714         return (ppChain ? DWFCORE_ALLOC_OBJECT(Iterator((*ppChain)->iterator(rSKey))) : NULL);
02715     }
02716 
02730     virtual ConstIterator* constIterator( const PK& rPKey, const SK& rSKey ) const
02731         throw()
02732     {
02733         DWFSkipList<SK, V, SE, SL, SZ>** ppChain = _oChains.find( rPKey );
02734 
02735         return (ppChain ? DWFCORE_ALLOC_OBJECT(ConstIterator((*ppChain)->constIterator(rSKey))) : NULL);
02736     }
02737 
02746     virtual V* find( const PK& rPKey, const SK& rSKey ) const
02747         throw()
02748     {
02749         DWFSkipList<SK, V, SE, SL, SZ>** ppChain = _oChains.find( rPKey );
02750 
02751         return (ppChain ? (*ppChain)->find(rSKey) : NULL);
02752     }
02753 
02761     virtual bool erase( const PK& rPKey )
02762         throw()
02763     {
02764         DWFSkipList<SK, V, SE, SL, SZ>** ppChain = _oChains.find( rPKey );
02765 
02766         //
02767         // forward the call
02768         //
02769         bool bErased = _oChains.erase( rPKey );
02770 
02771         if (*ppChain)
02772         {
02773             DWFCORE_FREE_OBJECT( *ppChain );
02774         }
02775 
02776         return bErased;
02777     }
02778 
02787     virtual bool erase( const PK& rPKey, const SK& rSKey )
02788         throw()
02789     {
02790         DWFSkipList<SK, V, SE, SL, SZ>** ppChain = _oChains.find( rPKey );
02791 
02792         return (ppChain ? (*ppChain)->erase(rSKey) : false);
02793     }
02794         
02795 
02808     virtual bool insert( const PK& rPKey, const SK& rSKey, const V& rValue, bool bReplace = true )
02809         throw( DWFException )
02810     {
02811         DWFSkipList<SK, V, SE, SL, SZ>** ppChain = _oChains.find( rPKey );
02812 
02813             //
02814             // add element into chain
02815             //
02816         if (ppChain)
02817         {
02818             return (*ppChain)->insert( rSKey, rValue, bReplace );
02819         }
02820             //
02821             // new chain
02822             //
02823         else
02824         {
02825             DWFSkipList<SK, V, SE, SL, SZ>* pNewChain = DWFCORE_ALLOC_OBJECT( (DWFSkipList<SK, V, SE, SL, SZ>) );
02826             
02827             if (pNewChain == NULL)
02828             {
02829                 _DWFCORE_THROW( DWFMemoryException, /*NOXLATE*/L"Failed to allocate chain" );
02830             }
02831 
02832             _oChains.insert( rPKey, pNewChain );
02833 
02834             return pNewChain->insert( rSKey, rValue, bReplace );
02835         }
02836     }
02837 
02838 private:
02839 
02840     DWFSkipList<PK, DWFSkipList<SK, V, SE, SL, SZ>*, PE, PL, PZ> _oChains;
02841 
02842 private:
02843 
02844     //
02845     // Not Implemented
02846     //
02847     DWFChainedSkipList( const DWFChainedSkipList& );
02848     DWFChainedSkipList& operator=( const DWFChainedSkipList& );
02849 };
02850 
02861 template<class V>
02862 class DWFCharKeyChainedSkipList : public DWFChainedSkipList<const char*, const char*, V, tDWFCharCompareEqual, tDWFCharCompareEqual, tDWFCharCompareLess, tDWFCharCompareLess>
02863                                 , virtual public DWFCoreMemory
02864 {
02865 public:
02866 
02867     DWFCharKeyChainedSkipList() throw() {;}
02868     virtual ~DWFCharKeyChainedSkipList() throw() {;}
02869 
02870 private:
02871 
02872     DWFCharKeyChainedSkipList( const DWFCharKeyChainedSkipList& );
02873     DWFCharKeyChainedSkipList& operator=( const DWFCharKeyChainedSkipList& );
02874 };
02875 
02886 template<class V>
02887 class DWFWCharKeyChainedSkipList : public DWFChainedSkipList<const wchar_t*, const wchar_t*, V, tDWFWCharCompareEqual, tDWFWCharCompareEqual, tDWFWCharCompareLess, tDWFWCharCompareLess>
02888                                  , virtual public DWFCoreMemory
02889 {
02890 public:
02891 
02892     DWFWCharKeyChainedSkipList() throw() {;}
02893     virtual ~DWFWCharKeyChainedSkipList() throw() {;}
02894 
02895 private:
02896 
02897     DWFWCharKeyChainedSkipList( const DWFWCharKeyChainedSkipList& );
02898     DWFWCharKeyChainedSkipList& operator=( const DWFWCharKeyChainedSkipList& );
02899 };
02900 
02911 template<class V>
02912 class DWFStringKeyChainedSkipList : public DWFChainedSkipList<DWFString, DWFString, V, 
02913                                                              tDWFCompareEqual<DWFString>, tDWFCompareEqual<DWFString>,
02914                                                              tDWFCompareLess<DWFString>, tDWFCompareLess<DWFString>,
02915                                                              tDWFStringDefinedEmpty, tDWFStringDefinedEmpty>
02916                                   , virtual public DWFCoreMemory
02917 {
02918 public:
02919 
02920     DWFStringKeyChainedSkipList() throw() {;}
02921     virtual ~DWFStringKeyChainedSkipList() throw() {;}
02922 
02923 private:
02924 
02925     DWFStringKeyChainedSkipList( const DWFStringKeyChainedSkipList& );
02926     DWFStringKeyChainedSkipList& operator=( const DWFStringKeyChainedSkipList& );
02927 };
02928 
02929 //
02930 // Delete allocated values in list type classes, namely DWFSkipList and DWFVector,
02931 // that provided the Iterator and ValueType typedefs.
02932 //
02933 // TODO: Add TypeTrait code to ensure that the value of the list are pointer types.
02934 template< class L >
02935 void DeleteAllocatedValuesInList( L& a )
02936 {
02937     typename L::Iterator* pIter = a.iterator();
02938     typename L::ValueType ptr = NULL;
02939 
02940     if (pIter)
02941     {
02942         for (; pIter->valid(); pIter->next())
02943         {
02944             ptr = pIter->value();
02945             DWFCORE_FREE_OBJECT( ptr );
02946         }
02947         DWFCORE_FREE_OBJECT( pIter );
02948     }
02949 }
02950 
02951 }
02952 
02953 #endif
02954 

Generated on Tue Jan 6 22:39:29 2009 for Autodesk DWF Core Library by  doxygen 1.4.5