[RC5] LIFO? Is this true?

Sanford Olson sanford at msn.fullfeed.com
Sat May 9 03:02:47 EDT 1998


You are making FIFO too hard!  It's quite easy:

OK, in the BUFF-IN file, for LIFO (a stack), you need to have a file
header, which contains the number of records in the file, file structure
version info, a pointer to the next record (top of the stack), etc.  The
pointer can be implied (i.e. it's always the last record in the file, etc).
 Then, you have a number of fixed-length records containing the RC5 block
info and a pointer to the next record (can be implied also - i.e. it's
always "current record" minus one).  To get a block, you have to lock the
file for exclusive access, read the fileheader, fetch the record indicated
by the fileheader, update and write the fileheader back to the file, and
finally unlock the file.  Adding a record to the file is similar.

For FIFO (a queue), it is almost as simple, but the fileheader contains
three pointers.  A "front" pointer which points to the "first record in the
list", a "back" pointer which points to the "last record in the list", and
a "deleted" pointer which points to a linked list (a stack) of records that
have been deleted and can now be reused.  So, when you get a record, you
get from the "front" of the list, update the "front" pointer to point to
the next record in the list, and add the current (just read) record to the
"deleted" stack:

   //Find and read first-in-list record
   RN = FileHeader.QFront;  ReadRecord(RN,&Data);

   //Make use of information in the record
   ... = Data.RC5Stuff;

   //Fix-up FileHeader and Deleted Record List
   FileHeader.QFront = Data.NextRecord;
   if (FileHeader.QFront == 0) FileHeader.QBack = 0;
   Data.NextRecord = FileHeader.DeletedRecordsList;
   FileHeader.DeletedRecordsList = RN;

When you add a record, you use a record from the "deleted" stack (if empty,
then add to end of file), point the current "back" record to this new
record, and point the "back" pointer to this new record:

   //Compute the Record Number of the new record
   if (FileHeader.DeletedRecordsList == 0) {
      //Deleted list is empty, add to end of file
      NewRN = ++FileHeader.nRecords;
   else {
      NewRN = FileHeader.DeletedRecordsList;
      FileHeader.DeletedRecordsList = Data.NextRecord;

   //Initialize and store new record
   Data.RC5Stuff = ...;
   Data.Next = 0;

   //Fix-up FileHeader and previous end-of-list record
   if (FileHeader.QBack == 0) FileHeader.QBack = FileHeader.QFront = NewRN;
   else {
      Data.NextRecord = NewRN;
      FileHeader.QBack = NewRN;

Anyway, it's basic Programming 101 - Linked-lists, Stacks, and Queues.
Except using record numbers instead of memory addresses as pointers.

- Sanford

At 10:09 PM 5/7/1998 , Phil Gregory wrote:
>> Well... Most operating systems don't support LIFO either.  They support
>> sequential reads/writes and positioning to a specific byte offset.  FIFO
>> takes about 10 minutes of extra coding compared to LIFO.
>The problems are in what to do after you've finished a block and where new
>blocks go.  After you've finished a LIFO block, you just move the file
>pointer back to point to the block before it.  The finished block can be
>discarded and/or ignored.  After you've finished a FIFO block, you either
>move the file pointer forward and leave some dead space at the beginning
>of the file or rewrite the entire file to remove the dead space.  The
>latter obviously causes a performance hit, especially with large buff-ins.
>The former, aside from being a really bad use of space, causes major
>problems when new blocks are added.  When blocks are added, where are they
>added?  LIFO always adds at the end--very easy.  FIFO rewriting the file
>every time also adds them at the end of the file, but the constant
>rewriting is bad anyway.  The other scenario for a FIFO either adds at
>the end or the beginning.  If at the end, then the file keeps growing and
>growing.  If at the beginning, what do you do if you have more blocks than
>room for them?
>In short, LIFO is a lot easier to implement.  I'd rather that the coders
>put their work into setting up v3 and keeping the creeping featureitis in
>the current clients to a minimum.

At 10:29 AM 5/8/1998, Michael K. Weise wrote:
>The way I'd remove a block from a FIFO buffer is to fill it with zeros, then
>compare total dead space to total file size and rewrite the entire file if
>dead space exceeds 50%. 

At 12:24 PM 5/8/1998, R. Kelley Cook
>Or you can keep a separate 1 bits per block map to keep track of which
>blocks have been loaded or checked plus each client keeps a pointer to
>the current block and then you would run through the blocks in a
>circular fashion.  This would have neither of your disadvantages and be
>mostly FIFO.  
>Main difference in code would be the config file itself could not hold
>the number of blocks to load, but this information could be easily
>determined from the file itself.  If the filesize is zero then it
>should autmatically run the initialization/resize routine would set up
>the file.
>0 - empty and/or already checked and results placed in buff-out.rc5
>1 - loaded but not completely checked

To unsubscribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net
rc5-digest subscribers replace rc5 with rc5-digest

More information about the rc5 mailing list