[Challenge] File-based Queue...
Posted on 2006-11-21
I'm working on a simple solution where I need to put items in a queue and retrieve them from it again. But this list needs to be persistent so the application will continue where it left off the next time I start it. Also, this queue can become huge with over half a million items or more so my solution is to use a file for storage.
The items I will store is just a single string. The contents of it will be XML containing the exact data of what I wanted to add to the stack. The data itself is not really important but right now my first approach is the following:
The first 8 bytes (INT64) of the file will give me the address of the first item in the list.
When pushing a new item to the queue, I just write 4 bytes with the string length, followed by the string itself.
When popping an item from the queue, I use the first 8 bytes to retrieve the starting point, read the length of the string and the string itself and increase the starting points with 4+length so it will point to the next record.
Drawback... I now have a history of items in my file and I would like this to be clean...
The current solution is simple... Once in a while I will just open the file, move the data closer to the beginning and truncate it past the last item. Not very complex but it's just something you don't want to do very often with a file of half a gigabyte in size or more. This packing of the "database" isn't really fast but it works. And in general I just pack it about every 512 pops or so.
So this makes me wonder about possible faster alternatives. Are there any? (Btw, this is already bloody fast...) So here is a new challenge. Make it work faster! :-)
Starting point is this:
TStack = class
procedure Push(Const Data: string);
function Pop: string;
Empty strings are NOT pushed to the file thus if there are no items in the queue then pop will just return an empty string indicating the end of the queue.
And no, am not providing the rest of my code. :-) It's a challenge, remember? I just described the solution.
(Btw, you could also turn this queue into a stack by writing the length TWICE to the file. Once before the string and once at the end of it. The Push function would be the same but popping items would have to read the last 4 bytes of the file to determine string length and then go back this length in the file to read the string. Then go back 4 + length + 4 bytes and truncate the file at that position. But for now I'm only interested in the Queue solution...)