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