contrib/src/fl/garbagec.cpp

   1 /////////////////////////////////////////////////////////////////////////////
   2 // Name:        garbagec.cpp
   3 // Purpose:     Garbage collection algorithm for optimizing refresh.
   4 // Author:      Aleksandras Gluchovas
   5 // Modified by:
   6 // Created:     18/10/98
   7 // RCS-ID:      $Id$
   8 // Copyright:   (c) Aleksandras Gluchovas
   9 // Licence:       wxWindows licence
  10 /////////////////////////////////////////////////////////////////////////////
  11
  12
  13 #ifdef __GNUG__
  14     #pragma implementation "garbagec.h"
  15 #endif
  16
  17 // For compilers that support precompilation, includes "wx/wx.h".
  18 #include "wx/wxprec.h"
  19
  20 #ifdef __BORLANDC__
  21 #pragma hdrstop
  22 #endif
  23
  24
  25 #ifndef WX_PRECOMP
  26 #include "wx/wx.h"
  27 #endif
  28
  29 #include "wx/fl/garbagec.h"
  30
  31 /***** Implementation for class GarbageCollector *****/
  32
  33 inline static GCItem& node_to_item( wxNode* pNode )
  34 {
  35     return *( (GCItem*)(pNode->GetData()) );
  36 }
  37
  38 GarbageCollector::~GarbageCollector()
  39 {
  40     Reset();
  41 }
  42
  43 /*** GC alg. helpers ***/
  44
  45 void GarbageCollector::DestroyItemList( wxList& lst )
  46 {
  47     wxNode* pNode = lst.GetFirst();
  48
  49     while( pNode )
  50     {
  51         delete &node_to_item( pNode );
  52
  53         pNode = pNode->GetNext();
  54     }
  55
  56     lst.Clear();
  57 }
  58
  59 wxNode* GarbageCollector::FindItemNode( void* pForObj )
  60 {
  61     wxNode* pNode = mAllNodes.GetFirst();
  62
  63     while( pNode )
  64     {
  65         if ( node_to_item( pNode ).mpObj == pForObj )
  66
  67             return pNode;
  68
  69         pNode = pNode->GetNext();
  70     }
  71
  72     int avoidCompilerWarning = 0;
  73     wxASSERT(avoidCompilerWarning); // DBG:: item should be present
  74
  75     return 0;
  76 }
  77
  78 wxNode* GarbageCollector::FindReferenceFreeItemNode()
  79 {
  80     wxNode* pNode = mAllNodes.GetFirst();
  81
  82     while( pNode )
  83     {
  84         if ( node_to_item( pNode ).mRefs.GetCount() == 0 )
  85
  86             return pNode;
  87
  88         pNode = pNode->GetNext();
  89     }
  90
  91     return 0;
  92 }
  93
  94 void GarbageCollector::RemoveReferencesToNode( wxNode* pItemNode )
  95 {
  96     wxNode* pNode = mAllNodes.GetFirst();
  97
  98     while( pNode )
  99     {
 100         wxList& refLst   = node_to_item( pNode ).mRefs;
 101         wxNode* pRefNode = refLst.GetFirst();
 102
 103         while( pRefNode )
 104         {
 105             if ( pRefNode->GetData() == (wxObject*)pItemNode )
 106             {
 107                 wxNode* pNext = pRefNode->GetNext();
 108
 109                 refLst.DeleteNode( pRefNode );
 110
 111                 pRefNode = pNext;
 112
 113                 continue;
 114             }
 115             else pRefNode = pRefNode->GetNext();
 116         }
 117
 118         pNode = pNode->GetNext();
 119     }
 120 }
 121
 122 void GarbageCollector::ResolveReferences()
 123 {
 124     wxNode* pNode = mAllNodes.GetFirst();
 125
 126     while( pNode )
 127     {
 128         GCItem& item = node_to_item( pNode );
 129
 130         wxNode* pRefNode = item.mRefs.GetFirst();
 131
 132         while( pRefNode )
 133         {
 134             pRefNode->SetData( (wxObject*) FindItemNode( (void*)pRefNode->GetData() ) );
 135
 136             pRefNode = pRefNode->GetNext();
 137         }
 138
 139         pNode = pNode->GetNext();
 140     }
 141 }
 142
 143 void GarbageCollector::AddObject( void* pObj, int WXUNUSED(refCnt) )
 144 {
 145     // FOR NOW:: initial ref-count is not used
 146
 147     GCItem* pItem = new GCItem();
 148
 149     pItem->mpObj  = pObj;
 150
 151     mAllNodes.Append( (wxObject*) pItem );
 152 }
 153
 154 void GarbageCollector::AddDependency( void* pObj, void* pDependsOnObj )
 155 {
 156     node_to_item( FindItemNode( pObj ) ).mRefs.Append( (wxObject*)pDependsOnObj );
 157 }
 158
 159 /*** GC alg. implementation ***/
 160
 161 void GarbageCollector::ArrangeCollection()
 162 {
 163     ResolveReferences();
 164
 165     do
 166     {
 167         // find node, which does not depend on anything
 168
 169         wxNode* pItemNode = FindReferenceFreeItemNode();
 170
 171         if ( pItemNode )
 172         {
 173             // append it to the list, where items are contained
 174             // in the increasing order of dependencies
 175
 176             mRegularLst.Append( pItemNode->GetData() );
 177
 178             mAllNodes.DeleteNode( pItemNode );
 179
 180             // remove references to this current "least-dependent" node
 181             // from reference lists of all the other nodes
 182
 183             RemoveReferencesToNode( pItemNode );
 184         }
 185         else
 186         {
 187             // otherwise, what is left - all nodes, which
 188             // are involved into cycled chains (rings)
 189
 190             wxNode* pNode = mAllNodes.GetFirst();
 191
 192             while( pNode )
 193             {
 194                 mCycledLst.Append( pNode->GetData() );
 195
 196                 pNode = pNode->GetNext();
 197             }
 198
 199             mAllNodes.Clear();
 200             break;
 201         }
 202
 203         // continue search for "least-dependent" nodes
 204
 205     } while(1);
 206 }
 207
 208 wxList& GarbageCollector::GetRegularObjects()
 209 {
 210     return mRegularLst;
 211 }
 212
 213 wxList& GarbageCollector::GetCycledObjects()
 214 {
 215     return mCycledLst;
 216 }
 217
 218 void GarbageCollector::Reset()
 219 {
 220     DestroyItemList( mAllNodes   );
 221     DestroyItemList( mRegularLst );
 222     DestroyItemList( mCycledLst );
 223 }
 224