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     return NULL;
  73 }
  74
  75 wxNode* GarbageCollector::FindReferenceFreeItemNode()
  76 {
  77     wxNode* pNode = mAllNodes.GetFirst();
  78
  79     while( pNode )
  80     {
  81         if ( node_to_item( pNode ).mRefs.GetCount() == 0 )
  82
  83             return pNode;
  84
  85         pNode = pNode->GetNext();
  86     }
  87
  88     return 0;
  89 }
  90
  91 void GarbageCollector::RemoveReferencesToNode( wxNode* pItemNode )
  92 {
  93     wxNode* pNode = mAllNodes.GetFirst();
  94
  95     while( pNode )
  96     {
  97         wxList& refLst   = node_to_item( pNode ).mRefs;
  98         wxNode* pRefNode = refLst.GetFirst();
  99
 100         while( pRefNode )
 101         {
 102             if ( pRefNode->GetData() == (wxObject*)pItemNode )
 103             {
 104                 wxNode* pNext = pRefNode->GetNext();
 105
 106                 refLst.DeleteNode( pRefNode );
 107
 108                 pRefNode = pNext;
 109
 110                 continue;
 111             }
 112             else pRefNode = pRefNode->GetNext();
 113         }
 114
 115         pNode = pNode->GetNext();
 116     }
 117 }
 118
 119 void GarbageCollector::ResolveReferences()
 120 {
 121     wxNode* pNode = mAllNodes.GetFirst();
 122
 123     while( pNode )
 124     {
 125         GCItem& item = node_to_item( pNode );
 126
 127         wxNode* pRefNode = item.mRefs.GetFirst();
 128
 129         while( pRefNode )
 130         {
 131             pRefNode->SetData( (wxObject*) FindItemNode( (void*)pRefNode->GetData() ) );
 132
 133             pRefNode = pRefNode->GetNext();
 134         }
 135
 136         pNode = pNode->GetNext();
 137     }
 138 }
 139
 140 void GarbageCollector::AddObject( void* pObj, int WXUNUSED(refCnt) )
 141 {
 142     // FOR NOW:: initial ref-count is not used
 143
 144     GCItem* pItem = new GCItem();
 145
 146     pItem->mpObj  = pObj;
 147
 148     mAllNodes.Append( (wxObject*) pItem );
 149 }
 150
 151 void GarbageCollector::AddDependency( void* pObj, void* pDependsOnObj )
 152 {
 153     node_to_item( FindItemNode( pObj ) ).mRefs.Append( (wxObject*)pDependsOnObj );
 154 }
 155
 156 /*** GC alg. implementation ***/
 157
 158 void GarbageCollector::ArrangeCollection()
 159 {
 160     ResolveReferences();
 161
 162     do
 163     {
 164         // find node, which does not depend on anything
 165
 166         wxNode* pItemNode = FindReferenceFreeItemNode();
 167
 168         if ( pItemNode )
 169         {
 170             // append it to the list, where items are contained
 171             // in the increasing order of dependencies
 172
 173             mRegularLst.Append( pItemNode->GetData() );
 174
 175             mAllNodes.DeleteNode( pItemNode );
 176
 177             // remove references to this current "least-dependent" node
 178             // from reference lists of all the other nodes
 179
 180             RemoveReferencesToNode( pItemNode );
 181         }
 182         else
 183         {
 184             // otherwise, what is left - all nodes, which
 185             // are involved into cycled chains (rings)
 186
 187             wxNode* pNode = mAllNodes.GetFirst();
 188
 189             while( pNode )
 190             {
 191                 mCycledLst.Append( pNode->GetData() );
 192
 193                 pNode = pNode->GetNext();
 194             }
 195
 196             mAllNodes.Clear();
 197             break;
 198         }
 199
 200         // continue search for "least-dependent" nodes
 201
 202     } while(1);
 203 }
 204
 205 wxList& GarbageCollector::GetRegularObjects()
 206 {
 207     return mRegularLst;
 208 }
 209
 210 wxList& GarbageCollector::GetCycledObjects()
 211 {
 212     return mCycledLst;
 213 }
 214
 215 void GarbageCollector::Reset()
 216 {
 217     DestroyItemList( mAllNodes   );
 218     DestroyItemList( mRegularLst );
 219     DestroyItemList( mCycledLst );
 220 }
 221