A queue is a data structure that supports manipulation of data sequentially. Items that need to be processed sequentially are put in the queue. The head of the queue contais the item that is next in line for processing, while the tail contains the item that will come last. This is all a basic queue can do: get the item that is next in line, and add a new item to the end of the queue.
LibDS's implemetation of a queue is more advanced than this: it is more of a linked-list. (Maybe it should be called a linked list, but it can play both roles without any problems.) LibDS refers to a queue as a QUEUE. In this LibDS implementation, the queue consists of nodes (called QELEMs), which contain all the administrative details required for the queue to operate properly, as well as the user data. You don't need necessarily need the QELEMs to be able to use a QUEUE.
As usual, items stored in the queue are void pointers to actual user data.
All data is stored in virtual memory.
QUEUE qMake(void)
Creates a new queue. The value returned is NULL if creation failed.
Closes the queue, effectively releasing all memory used by the queue. User data remains untouched, as usual (you will lose the pointer to it that the QUEUE was using to refer to it).
void qCloseWithFunction(QUEUE q, void (*fun)(void*))
Closes the queue, only this time call the function fun on each data element in the queue.
Adds an element to the tail of the queue. Returns a valid QELEM, or NULL if there was a problem (normally only if the implementation runs out of virtual memory). You can ignore the QELEM returned if you don't need the advanced functionality.
The currency of the queue points to this newly added element.
Removes the element that is next in line, and returns the data stored with it, or NULL on failure. Currency is not changed unless the current element is removed. In that case, the currency is lost.
The functions below do not actually remove, add or change the order of the queue elements. As usual, whenever a void* is returned, it contains user data, or NULL if something went wrong. Therefore, storing NULL as a value in the queue will not be distinguished from an error.
void* qFirst(QUEUE q)
Return the first element in the queue. Fails if the queue is empty. The currency is set to the first element in the queue.
void* qLast(QUEUE q)
Returns the last element in the queue. Fails if the queue is empty. The currencty is set to the last element in the queue.
void* qNext(QUEUE q)
Returns the next element in the queue. "Next" is defined as the element behind the current element in the queue. By convention, if there is no current item, the first item is returned. This effectively means that calling qNext() twice at the end of the queue will return the first element in the queue.
void* qPrev(QUEUE q)
Returns the previous element in the queue. "Previous" is defined as the element in front of the current element. By convention, if there is no current item, the last item is returned. This effectively means that calling qPrev() twice at the head of the queue will return the last element in the queue.
void* qCurrent(QUEUE q)
Returns the current item in the queue, or NULL if there's no current item.
void qClearCurrent(QUEUE q)
Clears the value of the current element. When this function returns the queue has no current element. This function always succeeds.
void qContains(QUEUE q, void *elem, void (*fun)(void*,void*))
If the queue contains the element elem, it is returned, else a NULL value is returned. The function fun takes as arguments two elements, and returns true if the elements are identical (a value other than zero), and false otherwise (a zero).
Return the number of elements in the queue.
int qEmpty(QUEUE q)
Returns 0 if the queue still has elements. Else a value not equal to zero is returned.
void qWalk(QUEUE q,void (*fun)(void*))
Visit all elements in the queue front-to-back, applying fun on each data item. Note that the same effect can be achieved through
for (data = qFirst(q); data; data = qNext(q))
process(data);
However, when this code finishes, the currency of the queue will be lost. qWalk(), on the other hand, will preserve the currency.
void qWalkAscending(QUEUE q,void (*fun)(void*))
Same as qWalk().
void qWalkDescending(QUEUE q,void (*fun)(void*))
Same as qWalk(), but the order of the visit is back-to-front. Note that this the same as
for (data = qLast(); data; data = qPrev())
process(data);
Here also the currency will be lost. qWalkDescending() will
not
change the currencty.
The queue consists of QELEM nodes. These nodes can be taken out of the queue, and inserted into it, without resorting to the rules imposed by the original queue: that only the front element is next in line to be processed, and all new elements are added at the end of the queue.
A new QELEM is created when a new data item is added to the queue, through qAdd() or qEnque(). All functions that return and integer, return -1 on failure and 0 on success.
int qElemAttach(QUEUE q,QELEM qElem)
Attach the given QELEM to the end of the queue.
int qElemInsert(QUEUE q,QELEM in_front_of,QELEM qElem)
Insert the given QELEM into the queue, at the position in front of the given qelem in_front_of. If that is NULL, then the element is appended to the queue.
int qElemDetach(QUEUE q,QELEM qElem)
Detach the given qElem from the queue.
void qElemFree(QELEM qElem)
Frees the memory associated with the given qElem.
void* qElemData(QELEM qElem)
Returns the user data pointer stored with this qElem. Returns NULL on failure.
QELEM qElemFirst(QUEUE q)
Returns the first qElem in the queue, NULL if it's not there.
QELEM qElemLast(QUEUE q)
Returns the last qElem in the queue, NULL if it's not there.
QELEM qElemNext(QELEM qElem)
Return the next qelem after this one. The funtion returns NULL if the current element is the last one.
QELEM qElemPrev(QELEM qElem)
Returns the qelem in front of this one. The funtion returns NULL if the current element is the first one.
void* qElemRemove(QUEUE q,QELEM qElem)
This one detaches the qElem from the queue, frees any memory associated with it, and returns the user data pointer that was stored with this qElem. NULL is returned on failure.