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: garbagec.cpp 35650 2005-09-23 12:56:45Z MR $ 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 28inline static GCItem& node_to_item( wxNode* pNode ) 29{ 30 return *( (GCItem*)(pNode->GetData()) ); 31} 32 33GarbageCollector::~GarbageCollector() 34{ 35 Reset(); 36} 37 38/*** GC alg. helpers ***/ 39 40void 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 54wxNode* 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 70wxNode* 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 86void 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 114void 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 135void 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 146void GarbageCollector::AddDependency( void* pObj, void* pDependsOnObj ) 147{ 148 node_to_item( FindItemNode( pObj ) ).mRefs.Append( (wxObject*)pDependsOnObj ); 149} 150 151/*** GC alg. implementation ***/ 152 153void 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 200wxList& GarbageCollector::GetRegularObjects() 201{ 202 return mRegularLst; 203} 204 205wxList& GarbageCollector::GetCycledObjects() 206{ 207 return mCycledLst; 208} 209 210void GarbageCollector::Reset() 211{ 212 DestroyItemList( mAllNodes ); 213 DestroyItemList( mRegularLst ); 214 DestroyItemList( mCycledLst ); 215} 216 217