The index queue is a linked list with extra fields for error recovery. Each item in the list is a fixed width field. The file is structured so that O(1) complexity is possible for push, pop, peek, and count operations. All file pointers (not FILE* but actual locations in the file) are platform dependent and are stored in machine byte order. File pointers are written to disk as the type long int, which, at the time of this writing, are 32 bits on some platforms and 64 on others.
The file is organized according to Figure 1. Each entry is given by Figure 2. The head pointer is the first entry in the queue, that is, the next entry to be removed from the queue. The tail pointer is the last entry in the queue. The free pointer is the last free entry in the queue. See Figure 3 for a graphical view of these pointers. The element count is the number of elements in the queue. This is necessary to determine when there are no more elements in the queue because head = tail is not enough. Head = tail is true when there is one element and when there is zero elements. The fields that begin with "last" are used for error recovery. They contain the values of their corresponding pointers at the time of the last successful operation.
------------------------------------------------------ | last operation (1 byte) | operation stage (1 byte) | ------------------------------------------------------ | head ptr | tail ptr | free ptr | element count | ---------------------------------------------------------------------- | last head ptr | last tail ptr | last free ptr | last element count | ---------------------------------------------------------------------- | save ptr 1 | ------------------------------------- | entry 1 | entry 2 | ... | entry N | ------------------------------------- Figure 1 - Field order
--------------------------------------------------------------- | next entry ptr | filename (32 bytes) | user data (64 bytes) | --------------------------------------------------------------- Figure 2 - Entry Format
Figure 3.
The last operation can have the following values:
The operation stage contains a value that corresponds to the stage an operation failed in.
Add and remove operations have different operation stages. Following is a discussion of the stages for each operation.
To begin an add operation, set last operation = 1 and set OS (operation stage) = 1.
Set save ptr 1 to free->next if free is not 0. Otherwise set save ptr 1 to 0. Set OS = 2.
if free = tail then
append new entry
if free = 0 then
set free = location of appended entry
set free->next = 0
else
set free->next = location of appended entry
set free = free->next
end
else if tail != 0
write entry at tail->next
else
write entry at free
end
if tail then
set tail = tail->next
else
set head = free;
set tail = free;
end
increment element count by 1
set OS = 3
Save last pointers. Set OS = 0. Set last operation = 0.
To begin a remove operation, set last operation = 2 and set OS = 1.
set save ptr 1 = free->next and set OS = 2.
if free != head then // If there is more than one queue item.
set free->next = head
set free = free->next
if tail = head
set tail = head->next
end
set head = head->next
set free->next = 0
else
set head = 0
set tail = 0
end
decrement element count by 1
set OS = 3
Save last pointers. set last operation = 0 and set OS = 0.
If an error occurs (power down, out of disk space, etc) while writing to the queue file then the last operation and the OS together will contain the enough information to restore the queue file to a consistent state.
The OS indicates which stage to recover from.
Set save ptr 1 = 0, set last operation to 0, and set CS = 0.
Restore head, tail, free, element count, and last free->next with last head, last tail, last free, last element count, and save ptr 1, respectively. Then set last operation = 0 and set OS = 0. At this point the entry may have been created, so we will lose some space. But this will rarely happen, it if ever happens at all, and can be reset by deleting the queue file.
Set last head, last tail, last free, and element count with head, tail, free, and element count repsectively. Then set last operation = 0 and set CS = 0.
Retry remove.
Restore from last variables, set last free->next = save ptr 1, and then retry remove.
Set save pointers. Set last operation = 0 and set OS = 0.