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