Deleting a single element from a binary file

[mgoldman]

I am working on a server application that must keep track of the messages that have been sent but not responded to.  After I send a message, I append it to an array cycling through an uninitialized shift register and I write it to the end of a binary file.  When I receive a response to a message, which was probably but not necessarily the first message sent, I delete that message from the array and the file.  This allows me to look up entries quickly but also to maintain a permanent record of what messages have been sent and not responded to.

Basically, I need an intelligent way to make a file, or any other permanent storage medium, act effectively like a queue.  The problem with the current implementation is that when I delete one variable-sized entry from the file, I need to move all subsequent entries, which are usually all of the other entries in the file, forward in memory to take its place.  Is there a way to get around recopying the majority of the file or to implement this entire thing more intelligently?

[MikeS81]

Hi brftskier...,

in which layer do you think? You can define the message length, like in databases, to define a fixed length in your file. If you have to delete a message write a marker into this field. If all fields from top to bottom are used, then you can add new messages at the end. If there are some fields with special markers, for deleted messages, then you can place the new messages there. This will only work if the order isn´t that necessary for you.

Hope it helps.

Mike

[mgoldman]

Thanks for the suggestion!  I was hoping to avoid creating and filling holes in my file because of the variable message body length, but I suppose that there is a theoretical maximum length to the messages my server would be sending.  That would also make my other task easier, which is maintaining a backlog of the last x responses received.  You've made me reconsider the option and, unless anyone else has a simple way to delete single entries from a binary file, the added complexity of adding messages to the file and the loss of generality in terms of the message length will be well worth the effort saved in deleting from the file.

[Nathan Vaidyanathan]

Hi,

Try deleting a single element from your cycling array and overwrite the entire array in your file. Every time you send a message you append it to an array cycling through a shift register.  When you recieve a response, delete the message in your array. When the array size is not equal to the previous value, you write the array to your binary file. Hope this helps.

[mgoldman]

Thanks for the suggestion.  That was how I had originally implemented it, but I decided that if the file's purpose is to provide a safe backup for the message list, I do not want to be overwriting the entire file at once.  Besides, now that I've standardized the message length and added a save/delete bit before every entry, it makes keeping a log of the last x messages much simpler.  Before, I had just let the log go out to 2x and then chopped it in half to save amortized time but now I can just keep overwriting the first x entries in order.

[Evgeny_Sviridov]

You can organize your datafile as a list. For example In this list any record consists of a fixed size data field and referencies (file position f.e.) to the next record and  to the previous record. You can then rewrite the record-have-to-be-deleted with new one, or you can "delete" this record modifiyng the referencies of the "previous" and the "next" records. When you will add a new record you can write one at this "free" place.

The other way is to manage two files. The first one contains your data record by record. The second one contains the numbers of the records and the corresponding datafile positions or record counter. This second file can be very small and easy-to-manage. It can represent the only record's queue position in the datafile. You can rewrite your records, mark them as deleted without moving large portions of data.

You can setup the datafile capacity in "number of records" term.

Additionally it is possible to use the records with variable length but it will be much more dificult. 

Best regards, Evgeny.