Making this non-recursive
This is a multi-part message in MIME format.
--------------090505060907010303040009
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
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
--------------090505060907010303040009
Content-Type: text/plain;
name="findtree.cpp"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
filename="findtree.cpp"
//
// File: findtree.cpp
// compile: cl findtree.cpp /W3 /GX /MD /D "_AFXDLL"
//
#include <stdio.h>
#include <afx.h>
#include <conio.h>
//---------------------------
// Hash Table
//---------------------------
const DWORD QXINDEX_MAXKEYLEN = 64;
const DWORD QXINDEX_HASHLIMIT = 4096;
const DWORD QXINDEX_LISTBLOCKSIZE = 16;
union TQXRef {
unsigned __int64 qword;
struct {
DWORD ref;
DWORD area;
} dword;
};
struct TListRecord {
DWORD Next;
TQXRef Ref;
};
struct TListBlock {
DWORD Next;
TQXRef Refs[QXINDEX_LISTBLOCKSIZE];
};
#pragma pack(1)
struct TTreeRecord {
DWORD Left;
DWORD Right;
TListRecord List;
BYTE KeyLen;
char Key[QXINDEX_MAXKEYLEN];
};
#pragma pack()
const char *qxfn = "marshall.qx";
DWORD HashTable[QXINDEX_HASHLIMIT] = {0};
//---------------------------
// Function Prototypes
//---------------------------
DWORD ReadAt(HANDLE &h, DWORD ofs, void *data, DWORD n);
DWORD WriteAt(HANDLE &h, DWORD ofs, const void *data, DWORD n);
BOOL FindTreeRecord(HANDLE &h, DWORD ofs, const TQXRef &qxr, int level);
BOOL FindRecord(HANDLE &h, const TQXRef &qxr);
BOOL FindRecord(HANDLE &h, const DWORD area, const DWORD ref);
HANDLE OpenQX(const char *fn);
BOOL CloseQX(HANDLE &h);
//---------------------------
// Main
//---------------------------
void main(char argc, char *argv[])
{
HANDLE hqx = OpenQX(qxfn);
if (hqx != INVALID_HANDLE_VALUE) {
try {
FindRecord(hqx,569, 1195264);
FindRecord(hqx,3, 10496);
} catch( ... ) {
printf("!! EXCEPTION: STACK OVERFLOW\n");
}
CloseQX(hqx);
}
}
DWORD ReadAt(HANDLE &h, DWORD ofs, void *data, DWORD n)
{
if (h == INVALID_HANDLE_VALUE) return 0;
DWORD cpos = SetFilePointer(h, ofs, NULL, FILE_BEGIN);
if (cpos != ofs) return 0;
DWORD z;
if (!ReadFile(h, data, n, &z, NULL)) {
return 0;
}
return z;
}
DWORD WriteAt(HANDLE &h, DWORD ofs, const void *data, DWORD n)
{
if (h == INVALID_HANDLE_VALUE) return 0;
SetFilePointer(h, ofs, NULL, FILE_BEGIN);
DWORD z;
if (!WriteFile(h, data, n, &z, NULL)) {
return 0;
}
if (z != n) {
return 0;
}
return z;
}
BOOL FindTreeRecord(HANDLE &h, DWORD ofs, const TQXRef &qxr, int level)
{
BOOL result = FALSE;
TTreeRecord tr;
if (ReadAt(h, ofs, &tr,sizeof(tr)) == 0) {
printf("! Error reading ofs: %d\n",ofs);
return 0;
}
if (tr.List.Ref.qword == qxr.qword) {
printf("# lvl: %3d a: %3d r: %7d [%s]\n",
level,
tr.List.Ref.dword.area,
tr.List.Ref.dword.ref,
tr.Key);
}
if (tr.List.Next) {
DWORD link = tr.List.Next;
while (link) {
TListBlock lb;
if (!ReadAt(h, link,&lb,sizeof(lb))) {
break;
}
for (DWORD i = 0; i < QXINDEX_LISTBLOCKSIZE; i++) {
if (qxr.qword ==lb.Refs[i].qword) {
printf("- lvl: %3d a: %3d r: %7d [%s]\n",
level,
lb.Refs[i].dword.area,
lb.Refs[i].dword.ref,
tr.Key);
}
}
link = lb.Next;
}
}
if (tr.Left) FindTreeRecord(h, tr.Left, qxr, level+1);
if (tr.Right) FindTreeRecord(h, tr.Right, qxr, level+1);
return TRUE;
}
BOOL FindRecord(HANDLE &h, const TQXRef &qxr)
{
if (ReadAt(h, 0,HashTable,sizeof(HashTable)) == 0) {
return FALSE;
}
for (DWORD i = 0; i < QXINDEX_HASHLIMIT; i++) {
DWORD ofs = HashTable[i];
if (ofs) FindTreeRecord(h, ofs, qxr, 0);
}
return TRUE;
}
BOOL FindRecord(HANDLE &h, const DWORD area, const DWORD ref)
{
TQXRef qxr;
qxr.dword.area = area;
qxr.dword.ref = ref;
return FindRecord(h,qxr);
}
HANDLE OpenQX(const char *fn)
{
HANDLE h = CreateFile(
fn,
GENERIC_READ|GENERIC_WRITE,
0,
NULL,
OPEN_ALWAYS,
FILE_ATTRIBUTE_NORMAL|FILE_FLAG_RANDOM_ACCESS,
0);
int err = GetLastError();
if (h != INVALID_HANDLE_VALUE) {
ZeroMemory(&HashTable, sizeof(HashTable));
if (GetFileSize(h, NULL) != 0) {
ReadAt(h, 0, HashTable, sizeof(HashTable));
} else {
// initialize
WriteAt(h, 0, HashTable, sizeof(HashTable));
}
}
return h;
}
BOOL CloseQX(HANDLE &h)
{
if (h != INVALID_HANDLE_VALUE) {
return CloseHandle(h);
}
return FALSE;
}
--------------090505060907010303040009--