Method for implementing a double-ended queue in a memory arrangement

• US 20020116568A1
• Filed: 12/10/2001
• Published: 08/22/2002
• Est. Priority Date: 06/10/1999
• Status: Active Grant

• Current Assignee: Nokia Technologies Oy (Nokia Corporation)
• Original Assignee: Nokia Corporation
• Inventors: Oksanen, Kenneth
• Granted Patent: US 6,742,091 B2
• Time in Patent Office: Days
• US Class Current: 711/101
• CPC Class Codes: G06F 7/785 having a sequence of storage locations each being individually accessible for both enqueue and dequeue operations, e.g. using a RAM

Abstract

The invention relates to a method for implementing a double-ended queue (deque) in a memory (MEM), and to a memory arrangement. To be able to reduce the amount of copying, particularly in functional environments, the double-ended queue is used in the memory as a hierarchic data structure where on the highest level of hierarchy, there is a three-element node of whose elements one points to the buffer forming the front end of the queue and another to the buffer forming the tail end of the queue. The middle of the queue consists of nodes on different levels of hierarchy so that pointing from each level of hierarchy to the next lower level of hierarchy is done by a pointer in the third element of a three-element node. The pointer points to a node on the next lower level of hierarchy which is a similar three-element node, with the exception of the lowest level of hierarchy where the said node can also be a buffer, and with the exception of the highest level of hierarchy, where the said pointer can also be a NIL pointer. Also the pointers in the two predetermined elements of the three-element node in the middle of the queue point to buffers. In the data structure, a buffer on a given level of hierarchy is treated as an element of a buffer on the next lower level of hierarchy. Adding (removing) elements to the queue is done at the buffers forming the front or tail end of the queue. A buffer which becomes full (or empty) in connection with adding (or removing) an element, is moved from one level of hierarchy to another.

Claims

1. 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,

characterised in that

a three-element node is used in the memory on the highest level of hierarchy, with its one element pointing to the buffer forming the beginning of the queue, and with its other element pointing to the buffer forming the tail end of the queue.

the middle of the queue is formed of nodes on successive levels of hierarchy so that a pointer contained in the third element of the three-element node on each level of hierarchy points to the next lower level of hierarchy so that the said pointer points to a node on the next lower level of hierarchy which is a similar three-element node, with the exception of the lowest level of hierarchy, where the said node can also be a buffer, and with the exception of the highest level of hierarchy, where the said buffer can also be a NIL pointer, when the two pre-determined elements of the three-element node in the middle of the queue contain a pointer to the buffer,

adding elements to the queue is done to a buffer forming either the head or tail end of the queue, and when the buffer being pointed to from the elements of a three-element node becomes full, it is moved to become an element in a buffer on the next lower level of hierarchy, and

removing elements from the queue is done to a buffer forming either the head or tail end of the queue, and when the buffer being pointed to from the elements of a three-element node becomes empty, a full buffer, being an element of a buffer on the next lower level of hierarchy, is fetched up from the said lower level of hierarchy to replace it.

2. A method according to claim 1, characterised in that a new level of hierarchy is created in the queue by forming a new one-element buffer in connection with adding an element, and this buffer is pointed to by a pointer contained in the third element of a three-element node on a higher level of hierarchy, and whose element the full buffer moved from the next higher level of hierarchy becomes.

3. A method according to claim 2, characterised in that the third element of a three-element node is its middle element.

4. A method according to claim 3, characterised in that buffers of the next higher level of hierarchy which have become full are added as elements to the said buffer until it becomes full, and in that the thus filled buffer is transformed, in connection with the next addition, into a three-element node with one of its elements pointing to the said full buffer.

5. A method according to claim 1, characterised in that the three-element node is transformed back into a buffer, if the buffer being pointed to by its predetermined element becomes full.

6. A method according to claim 1, characterised in that a maximum is predetermined for the number of elements in all the buffers in the queue.

7. A memory arrangement for implementing a double-ended queue (deque), which memory arrangement includes a data structure consisting of buffers,

characterised in that the data structure is formed of buffers on several different levels of hierarchy in such a way that

the highest level of hierarchy has a three-element node whose one element points to the buffer forming the front end of the queue and whose other element points to the buffer forming the tail end of the queue,

the middle of the queue consists of nodes on successive levels of hierarchy so that pointing from each level of hierarchy to the next lower level of hierarchy is done by the pointer in the third element in the three-element node so that the said pointer points to a node on the next lower level of hierarchy that is a similar three-element node, with the exception of the lowest level of hierarchy where the said node can also be a buffer, and with the exception of the highest level of hierarchy where the said pointer can also be a NIL pointer, when also two of the elements in the three-element node in the middle of the queue contain a pointer that points to a buffer,

a buffer on a given level of hierarchy is treated as an element of a buffer on the next lower level of hierarchy.

8. A memory arrangement according to claim 7, characterised in that the third element of a three-element node is its middle element.

9. A memory arrangement according to claim 7, characterised in that only the buffers forming the front and tail end of a queue and buffers pointed to from the predetermined elements of a three-element node can be non-full.

10. A memory arrangement according to claim 7, characterised in that buffers do not contain non-full buffers.

11. A memory arrangement according to claim 7, characterised in that all buffers in the queue have the same, predetermined maximum for their number of elements.