Re: Making this non-recursive - SOLVED
Phew! PROBLEM SOLVED using a STACK approach!
The stack class:
class CStackNumber : public CList< DWORD, DWORD>
{
public:
void Push( DWORD n )
{ AddHead( n ); }
BOOL Pop(DWORD &n)
{
if (IsEmpty()) return FALSE;
n = RemoveHead();
return TRUE;
}
};
and the changes the findtree.cpp code:
CStackNumber ofsStack; //NEW
BOOL FindTreeRecord(HANDLE &h, DWORD ofs, const TQXRef &qxr, int level)
{
//===== NEW! Don't let the recursive get over 100 levels
if (level > 100) {
ofsStack.Push(ofs);
return TRUE;
}
//=====
....
}
BOOL FindRecord(HANDLE &h, const TQXRef &qxr)
{
....
//===== NEW, finish up!
DWORD ofs;
while (ofsStack.Pop(ofs)) {
DumpTreeRecord(h,ofs,qxr,0);
}
//=====
return TRUE;
}
--
HLS
Pops wrote:
Folks,
I am in short urgent timeline to get this completed and I desperately
need a good student of C/C++ computer science to assist me here.
I recently found a stack overflow situation and need to correctly make
the following recursive code - non-recursive, specifically the
FindTreeRecord() function.
I attached findtree.cpp with the C/C++ source code. I wanted to attach
an example data file to work with, but it was too large for this post so
I made it available at:
http://beta.winserver.com/public/test/marshall.zip
The main() code has an example deep record to find in the qx file.
This HashTable code was designed back in 1996 by a former computer
science engineer no longer with us and I guess today with larger users,
with deeper nodes in the hash tree, the recursive nature of it is now
revealing the stack overflow problem.
The FindTreeRecord() is only used to clear specific nodes in the tree.
In the zip, this cut down version simply prints out the found node. But
in reality, it would clear the node and update the data file. IOW, the
true goal of the function is to "Clear" the node during an update process.
Some testing details:
The example record search shown in the main() code, should provide 4
hits, in an unknown order:
[filename]
[SYSTEM]
[ADDED]
[FILE]
If you explore this, you will see that I am passing the recursive level
so it is printed with each find. You will see it will go pretty deep
when a stack overflow occurs. If you put a limit like so in the
FindTreeRecord() function;
if (tr.Left && level<100)
FindTreeRecord(h, tr.Left, qxr, level+1);
if (tr.Right && level<100)
FindTreeRecord(h, tr.Right, qxr, level+1);
You will see that it might find some nodes but not all without the stack
problem.
The only issue I have is when traversing the tree recursively to find
all nodes with a specfic TQXRef value. I would greatly appreciate
assistance in making this function non-recursive.
Thanks in Advance
PS: I am going to switch to a SQL database system, but I need this fixed
now until the new SQL version is available.
--
HLS