Changeset 11285 for OpenSceneGraph/trunk/src/osgDB/DatabasePager.cpp

Timestamp:

03/24/10 15:27:00 (3 years ago)

Author:

robert

Message:

Refactored the way that the RequestQueue?'s are pruned and highest prioty items taken from them so the operation is
now O(n) rather than O(nlogn) where n is the number of requests. The refactoring also cleans up the access of the
request lists so that the code is more readable/maintainable.

Files:

• OpenSceneGraph/trunk/src/osgDB/DatabasePager.cpp (modified) (19 diffs)

OpenSceneGraph/trunk/src/osgDB/DatabasePager.cpp

@@ -282 +282 @@
 //  RequestQueue
 //
+DatabasePager::RequestQueue::RequestQueue(DatabasePager* pager):
+    _pager(pager),
+    _frameNumberLastPruned(-1)
+{
+}
+
+DatabasePager::RequestQueue::~RequestQueue()
+{
+    OSG_INFO<<"DatabasePager::RequestQueue::~RequestQueue() Destructing queue."<<std::endl;
+    for(RequestList::iterator itr = _requestList.begin();
+        itr != _requestList.end();
+        ++itr)
+    {
+        (*itr)->invalidate();
+    }
+}
+
 void DatabasePager::DatabaseRequest::invalidate()
 {
@@ -292 +309 @@
 }
 
-DatabasePager::RequestQueue::~RequestQueue()
-{
-    OSG_INFO<<"DatabasePager::RequestQueue::~RequestQueue() Destructing queue."<<std::endl;
-    for(RequestList::iterator itr = _requestList.begin();
-        itr != _requestList.end();
-        ++itr)
-    {
-        (*itr)->invalidate();
-    }
-}
-
-void DatabasePager::RequestQueue::sort()
-{
-    std::sort(_requestList.begin(),_requestList.end(),SortFileRequestFunctor());
-}
-
+bool DatabasePager::RequestQueue::pruneOldRequestsAndCheckIfEmpty()
+{
+    OpenThreads::ScopedLock<OpenThreads::Mutex> lock(_requestMutex);
+
+    if (_frameNumberLastPruned != _pager->_frameNumber)
+    {
+        for(RequestQueue::RequestList::iterator citr = _requestList.begin();
+            citr != _requestList.end();
+            )
+        {
+            if ((*citr)->isRequestCurrent(_pager->_frameNumber))
+            {
+                ++citr;
+            }
+            else
+            {
+                (*citr)->invalidate();
+
+                citr = _requestList.erase(citr);
+                OSG_INFO<<"DatabasePager::RequestQueue::pruneOldRequestsAndCheckIfEmpty(): Pruning "<<(*citr)<<std::endl;
+            }
+        }
+
+        _frameNumberLastPruned = _pager->_frameNumber;
+
+        updateBlock();
+    }
+
+    return _requestList.empty();
+}
+
+
+void DatabasePager::RequestQueue::clear()
+{
+    OpenThreads::ScopedLock<OpenThreads::Mutex> lock(_requestMutex);
+
+    for(RequestList::iterator citr = _requestList.begin();
+        citr != _requestList.end();
+        ++citr)
+    {
+        (*citr)->invalidate();
+    }
+
+    _requestList.clear();
+
+    _frameNumberLastPruned = _pager->_frameNumber;
+
+    updateBlock();
+}
+
+
+void DatabasePager::RequestQueue::add(DatabasePager::DatabaseRequest* databaseRequest)
+{
+    OpenThreads::ScopedLock<OpenThreads::Mutex> lock(_requestMutex);
+
+    _requestList.push_back(databaseRequest);
+    databaseRequest->_requestQueue = this;
+
+    updateBlock();
+}
+
+void DatabasePager::RequestQueue::takeFirst(osg::ref_ptr<DatabaseRequest>& databaseRequest)
+{
+    OpenThreads::ScopedLock<OpenThreads::Mutex> lock(_requestMutex);
+
+    if (!_requestList.empty())
+    {
+        DatabasePager::SortFileRequestFunctor highPriority;
+
+        RequestQueue::RequestList::iterator selected_itr = _requestList.end();
+
+        for(RequestQueue::RequestList::iterator citr = _requestList.begin();
+            citr != _requestList.end();
+            )
+        {
+            if ((*citr)->isRequestCurrent(_pager->_frameNumber))
+            {
+                if (selected_itr==_requestList.end() || highPriority(*citr, *selected_itr))
+                {
+                    selected_itr = citr;
+                }
+
+                ++citr;
+            }
+            else
+            {
+                (*citr)->invalidate();
+
+                citr = _requestList.erase(citr);
+                OSG_INFO<<"DatabasePager::RequestQueue::takeFirst(): Pruning "<<(*citr)<<std::endl;
+            }
+
+        }
+
+        _frameNumberLastPruned = _pager->_frameNumber;
+
+        if (selected_itr != _requestList.end())
+        {
+            databaseRequest = *selected_itr;
+            databaseRequest->_requestQueue = 0;
+            _requestList.erase(selected_itr);
+            OSG_INFO<<" DatabasePager::RequestQueue::takeFirst() Found DatabaseRequest size()="<<_requestList.size()<<std::endl;
+        }
+        else
+        {
+            OSG_INFO<<" DatabasePager::RequestQueue::takeFirst() No suitable DatabaseRequest found size()="<<_requestList.size()<<std::endl;
+        }
+
+        updateBlock();
+    }
+}
 
 /////////////////////////////////////////////////////////////////////////////////////////////////////////////////
@@ -314 +426 @@
 //
 DatabasePager::ReadQueue::ReadQueue(DatabasePager* pager, const std::string& name):
-    _pager(pager),
-    _name(name),
-    _frameNumberLastPruned(-1)
+    RequestQueue(pager),
+    _name(name)
 {
     _block = new osg::RefBlock;
 }
 
-void DatabasePager::ReadQueue::clear()
-{
-    OpenThreads::ScopedLock<OpenThreads::Mutex> lock(_requestMutex);
-
-    for(RequestList::iterator citr = _requestList.begin();
-        citr != _requestList.end();
-        ++citr)
-    {
-        (*citr)->invalidate();
-    }
-
-    _requestList.clear();
-
-    updateBlock();
-}
-
-void DatabasePager::ReadQueue::add(DatabasePager::DatabaseRequest* databaseRequest)
-{
-    OpenThreads::ScopedLock<OpenThreads::Mutex> lock(_requestMutex);
-    _requestList.push_back(databaseRequest);
-    databaseRequest->_requestQueue = this;
-
-    updateBlock();
-}
-
-void DatabasePager::ReadQueue::takeFirst(osg::ref_ptr<DatabaseRequest>& databaseRequest)
-{
-    OpenThreads::ScopedLock<OpenThreads::Mutex> lock(_requestMutex);
-
-    if (!_requestList.empty())
-    {
-        sort();
-
-        if (_frameNumberLastPruned != _pager->_frameNumber)
-        {
-            // Prune all the old entries.
-            RequestQueue::RequestList::iterator tooOld
-                = std::find_if(_requestList.begin(),
-                                _requestList.end(),
-                                refPtrAdapt(std::not1(std::bind2nd(std::mem_fun(&DatabaseRequest::isRequestCurrent),
-                                _pager->_frameNumber))));
-
-            // delete the entries
-            for(RequestQueue::RequestList::iterator citr = tooOld;
-                citr != _requestList.end();
-                ++citr)
-            {
-                (*citr)->invalidate();
-            }
-
-            _requestList.erase(tooOld, _requestList.end());
-
-            _frameNumberLastPruned = _pager->_frameNumber;
-        }
-
-        if (!_requestList.empty())
-        {
-            databaseRequest = _requestList.front();
-            databaseRequest->_requestQueue = 0;
-            _requestList.erase(_requestList.begin());
-        }
-
-        updateBlock();
-    }
+void DatabasePager::ReadQueue::updateBlock()
+{
+    _block->set((!_requestList.empty() || !_childrenToDeleteList.empty()) &&
+                !_pager->_databasePagerThreadPaused);
 }
 
@@ -712 +763 @@
                 if (loadedObjectsNeedToBeCompiled)
                 {
-                    OpenThreads::ScopedLock<OpenThreads::Mutex> lock(_pager->_dataToCompileList->_requestMutex);
-                    databaseRequest->_requestQueue = _pager->_dataToCompileList.get();
-                    _pager->_dataToCompileList->_requestList.push_back(databaseRequest);
+                    _pager->_dataToCompileList->add(databaseRequest.get());
                 }
                 else
                 {
-                    OpenThreads::ScopedLock<OpenThreads::Mutex> lock(_pager->_dataToMergeList->_requestMutex);
-                    databaseRequest->_requestQueue = _pager->_dataToMergeList.get();
-                    _pager->_dataToMergeList->_requestList.push_back(databaseRequest);
+                    _pager->_dataToMergeList->add(databaseRequest.get());
                 }
-            }        
+            }
 
             // Prepare and prune the to-be-compiled list here in
@@ -729 +776 @@
             if (loadedObjectsNeedToBeCompiled)
             {
-                OpenThreads::ScopedLock<OpenThreads::Mutex> lock(_pager->_dataToCompileList->_requestMutex);
-
-                _pager->_dataToCompileList->sort();
-
-                // Prune all the old entries.
-                RequestQueue::RequestList::iterator tooOld
-                    = std::find_if(_pager->_dataToCompileList->_requestList.begin(),
-                                   _pager->_dataToCompileList->_requestList.end(),
-                                   refPtrAdapt(std::not1(std::bind2nd(std::mem_fun(&DatabaseRequest::isRequestCurrent),
-                                   _pager->_frameNumber))));
-
-                // This is the database thread, so just delete
-                for(RequestQueue::RequestList::iterator citr = tooOld;
-                    citr != _pager->_dataToCompileList->_requestList.end();
-                    ++citr)
-                {
-                    OSG_INFO<<_name<<": pruning from compile list"<<std::endl;
-                    (*citr)->_loadedModel = 0;
-                    (*citr)->_requestQueue = 0;
-                }
-
-                _pager->_dataToCompileList->_requestList.erase(tooOld, _pager->_dataToCompileList->_requestList.end());
-
-                loadedObjectsNeedToBeCompiled = !_pager->_dataToCompileList->_requestList.empty();
+                loadedObjectsNeedToBeCompiled = ! _pager->_dataToCompileList->pruneOldRequestsAndCheckIfEmpty();
             }
 
@@ -972 +996 @@
     _httpRequestQueue = new ReadQueue(this,"httpRequestQueue");
     
-    _dataToCompileList = new RequestQueue;
-    _dataToMergeList = new RequestQueue;
+    _dataToCompileList = new RequestQueue(this);
+    _dataToMergeList = new RequestQueue(this);
     
     setUpThreads(
@@ -1020 +1044 @@
     _httpRequestQueue = new ReadQueue(this,"httpRequestQueue");
     
-    _dataToCompileList = new RequestQueue;
-    _dataToMergeList = new RequestQueue;
+    _dataToCompileList = new RequestQueue(this);
+    _dataToMergeList = new RequestQueue(this);
 
     for(DatabaseThreadList::const_iterator dt_itr = rhs._databaseThreads.begin();
@@ -1174 +1198 @@
     _fileRequestQueue->clear();
     _httpRequestQueue->clear();
-        
-    {
-        OpenThreads::ScopedLock<OpenThreads::Mutex> lock(_dataToCompileList->_requestMutex);
-        for(RequestQueue::RequestList::iterator citr = _dataToCompileList->_requestList.begin();
-            citr != _dataToCompileList->_requestList.end();
-            ++citr)
-        {
-            (*citr)->_loadedModel = 0;
-            (*citr)->_requestQueue = 0;
-        }
-        _dataToCompileList->_requestList.clear();
-    }
-
-    {
-        OpenThreads::ScopedLock<OpenThreads::Mutex> lock(_dataToMergeList->_requestMutex);
-        for(RequestQueue::RequestList::iterator citr = _dataToMergeList->_requestList.begin();
-            citr != _dataToMergeList->_requestList.end();
-            ++citr)
-        {
-            (*citr)->_loadedModel = 0;
-            (*citr)->_requestQueue = 0;
-        }
-        _dataToMergeList->_requestList.clear();
-    }
+
+    _dataToCompileList->clear();
+    _dataToMergeList->clear();
 
     // note, no need to use a mutex as the list is only accessed from the update thread.
@@ -1282 +1285 @@
     {
         DatabaseRequest* databaseRequest = dynamic_cast<DatabaseRequest*>(databaseRequestRef.get());
-        if (databaseRequest && databaseRequest->valid())
-        {
-            OSG_NOTICE<<"DatabaseRequest has been previously invalidated whilst still attached to scene graph."<<std::endl;
+        if (databaseRequest && !(databaseRequest->valid()))
+        {
+            OSG_INFO<<"DatabaseRequest has been previously invalidated whilst still attached to scene graph."<<std::endl;
             databaseRequest = 0;
         }
@@ -1297 +1300 @@
                 OpenThreads::ScopedLock<OpenThreads::Mutex> lock(requestQueue->_requestMutex);
 
+                databaseRequest->_valid = true;
                 databaseRequest->_frameNumberLastRequest = frameNumber;
                 databaseRequest->_timestampLastRequest = timestamp;
@@ -1304 +1308 @@
             else
             {
+                databaseRequest->_valid = true;
                 databaseRequest->_frameNumberLastRequest = frameNumber;
                 databaseRequest->_timestampLastRequest = timestamp;
@@ -1316 +1321 @@
                 OSG_INFO<<"DatabasePager::requestNodeFile("<<fileName<<") orphaned, resubmitting."<<std::endl;
 
+                databaseRequest->_valid = true;
                 databaseRequest->_frameNumberFirstRequest = frameNumber;
                 databaseRequest->_timestampFirstRequest = timestamp;
@@ -1345 +1351 @@
             databaseRequestRef = databaseRequest.get();
 
+            databaseRequest->_valid = true;
             databaseRequest->_fileName = fileName;
             databaseRequest->_frameNumberFirstRequest = frameNumber;
@@ -1422 +1429 @@
 bool DatabasePager::requiresUpdateSceneGraph() const
 {
-    {
-        OpenThreads::ScopedLock<OpenThreads::Mutex> lock(_dataToMergeList->_requestMutex);
-        if (!_dataToMergeList->_requestList.empty()) return true;
-    }
-    
-    return false;
-    
+#if 0
+    OpenThreads::ScopedLock<OpenThreads::Mutex> lock(_dataToMergeList->_requestMutex);
+#endif
+    return !(_dataToMergeList->_requestList.empty());
 }
 
@@ -1458 +1462 @@
 #ifdef UPDATE_TIMING
     double elapsedTime = timer.elapsedTime_m();
-    if (elapsedTime>0.2)
+    if (elapsedTime>1.0)
     {
         OSG_NOTICE<<"DatabasePager::updateSceneGraph() total time = "<<elapsedTime<<"ms"<<std::endl;
@@ -1835 +1839 @@
 bool DatabasePager::requiresCompileGLObjects() const
 {
+#if 0
     OpenThreads::ScopedLock<OpenThreads::Mutex> lock(_dataToCompileList->_requestMutex);
+#endif
     return !_dataToCompileList->_requestList.empty();
 }
@@ -1905 +1911 @@
 
         osg::ref_ptr<DatabaseRequest> databaseRequest;
-
-        // get the first compilable entry.
-        {
-            OpenThreads::ScopedLock<OpenThreads::Mutex> lock(_dataToCompileList->_requestMutex);
-        
-            // advance to the next entry to compile if one is available.
-            databaseRequest = _dataToCompileList->_requestList.empty() ? 0 : _dataToCompileList->_requestList.front().get();
-        };
+        _dataToCompileList->takeFirst(databaseRequest);
 
         unsigned int numObjectsCompiled = 0;
@@ -1918 +1917 @@
         // while there are valid databaseRequest's in the to compile list and there is
         // sufficient time left compile each databaseRequest's stateset and drawables.
-        while (databaseRequest.valid() && (compileAll || (elapsedTime<availableTime && numObjectsCompiled<_maximumNumOfObjectsToCompilePerFrame)) ) 
+        while (databaseRequest.valid() && databaseRequest->valid() && (compileAll || (elapsedTime<availableTime && numObjectsCompiled<_maximumNumOfObjectsToCompilePerFrame)) )
         {
             DataToCompileMap& dcm = databaseRequest->_dataToCompileMap;
@@ -2028 +2027 @@
                 // we've compiled all of the current databaseRequest so we can now pop it off the
                 // to compile list and place it on the merge list.
-                // OSG_NOTICE<<"All compiled"<<std::endl;
-
-
-                OpenThreads::ScopedLock<OpenThreads::Mutex> lock(_dataToCompileList->_requestMutex);
-
-                // The request might have been removed from the
-                // _dataToCompile list by another graphics thread, in
-                // which case it's already on the merge list, or by
-                // the pager, which means that the request has
-                // expired. Also, the compile list might have been
-                // shuffled by the pager, so the current request is
-                // not guaranteed to still be at the beginning of the
-                // list.
-                
-                RequestQueue::RequestList::iterator requestIter
-                    = std::find(_dataToCompileList->_requestList.begin(), _dataToCompileList->_requestList.end(),
-                           databaseRequest);
-                if (requestIter != _dataToCompileList->_requestList.end())
-                {
-                    {
-                        OpenThreads::ScopedLock<OpenThreads::Mutex> lock(_dataToMergeList->_requestMutex);
-                        databaseRequest->_requestQueue = _dataToMergeList.get();
-                        _dataToMergeList->_requestList.push_back(databaseRequest);
-                    }
-                    _dataToCompileList->_requestList.erase(requestIter);
-                }
-                
-                if (!_dataToCompileList->_requestList.empty()) databaseRequest = _dataToCompileList->_requestList.front();
-                else databaseRequest = 0;
-
-            }
-            else 
-            {
-                // OSG_NOTICE<<"Not all compiled"<<std::endl;
+                OSG_INFO<<"All compiled"<<std::endl;
+
+                _dataToMergeList->add(databaseRequest.get());
+
+                databaseRequest = 0;
+                _dataToCompileList->takeFirst(databaseRequest);
+            }
+            else
+            {
+                OSG_INFO<<"Not all compiled"<<std::endl;
+                _dataToCompileList->add(databaseRequest.get());
                 databaseRequest = 0;
             }