Patent ID: 6742091
Filing Date: 2004-05-25
Classification: G06F

Abstract:
A method for implementing a double-ended queue (deque) in a memory where information is stored as data units and each element is allocated its own memory space, in which method data units are added to and removed from the queue according to the LIFO or FIFO principle in such a way that data units are added to or removed from either the beginning or the end of the queue, whereinthere is used in the memory on highest level of hierarchy a three-element node having a first element pointing to a first buffer forming a front end of the queue, a second element pointing to a second buffer forming a tail end of the queue, and a third element containing a pointer to a node on a next lower level of hierarchy or a NIL pointer, a middle of the queue is formed of three-element nodes on successive levels of hierarchy, said three-element nodes in the middle of the queue being similar to the three-element node on the highest level of hierarchy and each three-element node in the middle of the queue having first and second elements each containing a pointer to a respective further buffer and a third element containing a pointer to a node on a next lower level of hierarchy, at a lowest level of hierarchy there is used a node, which is a buffer or a three-element node having first and second elements each containing a pointer to a respective further buffer and a third element containing a NIL pointer, adding data units to the queue is done to one of the first and second buffer forming either the front or tail end of the queue, and when the one buffer being pointed to from the elements of a three-element node becomes full, the one buffer is moved to become an element in a third buffer on the next lower level of hierarchy, and removing data units from the queue is done to one of the first and second buffer forming either the front or tail end of the queue, and when the one buffer being pointed to from the elements of a three-element node becomes empty, a full buffer, being an element of a third buffer on the next lower level of hierarchy, is fetched up from the next lower level of hierarchy to replace it.