From: pjfarley AT banet DOT net (Peter J. Farley III)
Newsgroups: comp.os.msdos.djgpp
Subject: OT: Looking for help with data structure recovery...
Date: Mon, 22 May 2000 00:58:00 GMT
Message-ID: <392880dc.2153977@news3.banet.net>
X-Newsreader: Forte Free Agent 1.21/32.243
NNTP-Posting-Host: 32.100.84.122
X-Trace: 22 May 2000 00:56:26 GMT, 32.100.84.122
Organization: Global Network Services - Remote Access Mail & News Services
Lines: 48
X-Complaints-To: abuse AT prserv DOT net
To: djgpp AT delorie DOT com
DJ-Gateway: from newsgroup comp.os.msdos.djgpp
Reply-To: djgpp AT delorie DOT com

I already posted this over on comp.databases.theory, but haven't
gotten any answer there yet.  If anyone here knows where or who could
answer me, I'd appreciate your help.  Even references to books or
academic papers would be appreciated.

I've done quite a bit of web searching over the last few days, and
haven't found any references to recovery algorithims.  Though there is
a lot of "data structure" material out there, most of it is either
creation or access algorithims.  I haven't yet found any references
for the recovery of broken external structures.

TIA for any help or pointers to sources you can provide.

P.S. -- This is not an academic or student exercise, but a real-world
requirement for a rather large and highly complex application that is
not-quite-ready for a real "database" implementation yet.

<=========Original post to comp.databases.theory===================>
Are there any generalized structure recovery algorithims for a simple
linked list file structure?  I.E., in the event of application
failure, OS failure, power failure, etc., are there any generalized
algorithims to scan a (possibly broken-link) external data file and
recover the original (or last-successful-update) linked list
structure?

The application in question uses the following steps to attempt to
safely insert new data blocks into the linked list of blocks. 
Pointers are relative block numbers, and the data are stored in
fixed-length blocks.  No deletions are done dynamically, though there
is a remove-old-data-and-rebuild program that is used to reorganize
the file offline.  The rebuild process is safe because the original
file is preserved.  The reorganized file is written as a new file, so
the rebuild process can always be restarted from scratch.

1.	Mark block preceding insert with "insert in progress" flag and
rewrite it.

2.	Select empty block number and write new data to new block,
filling chain pointer with block number of logically following block.

3.	Unmark block preceding insert and change block pointer to
point to new block already written, and then rewrite this block.

TIA for any info or advice you can offer.

----------------------------------------------------
Peter J. Farley III (pjfarley AT nospam DOT dorsai DOT org OR
                     pjfarley AT nospam DOT banet DOT net)