Method for implementing a queue in a memory, and memory arrangement

• US 6,374,339 B2
• Filed: 03/02/2001
• Issued: 04/16/2002
• Est. Priority Date: 09/08/1998
• Status: Expired due to Term

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Nokia Networks (Nokia Corporation)
• Inventors: Iivonen, Jukka-Pekka
• Primary Examiner(s): Elmore, Reba I.
• Application Number:
  US09/798,371
• Publication Number:
  US 20010021964A1
• Time in Patent Office: 410 Days
• Field of Search: 711/165, 711/170
• US Class Current: 711/170
• CPC Class Codes: G06F 13/1642 with request queuing

Abstract

The invention relates to a method for implementing a queue, particularly a FIFO queue, in a memory (MEM) and to a memory arrangement. In order to enable reducing the amount of copying particularly in a functional environment, at least part of the queue is formed with a tree-shaped data structure (A, B) known per se, having nodes at several different hierarchy levels, wherein an individual node can be (i) an internal node (N1-N3) containing at least one pointer pointing to a node lower in the tree-shaped hierarchy or (ii) a leaf node (N4-N6) containing at least one pointer to data unit (1 . . . 6) stored in the memory or at least one data unit. A given maximum number of pointers that an individual node can contain is defined for the nodes. The additions to be made to said part are directed in the tree-shaped data structure to the first non-full node (N4), seen from below, on a predetermined first edge of the data structure and they are further implemented in such a way that the leaf nodes remain at the same hierarchy level of the tree-shaped data structure, wherein when a non-full node is not present, new nodes are created to maintain the leaf nodes at the same hierarchy level. The deletions to be made from said part are typically directed to the leaf node on the opposite edge of the tree.

Claims

1. A method for implementing a queue in a memory (MEM) in which data is stored as data units for each of which a dedicated storage space is assigned in the memory, in accordance with which method data units are added to and deleted from the queue,

characterized in that

at least part of the queue is implemented as a tree-shaped data structure (A, B) known per se, having nodes at several different hierarchy levels, wherein an individual node can be (i) an internal node containing at least one pointer pointing to a node lower in the tree-shaped hierarchy or (ii) a leaf node containing at least one pointer to a data unit stored in the memory, wherein the node at the highest level of the structure is the root node of the structure, and wherein in connection with the addition of a data unit a pointer pointing to said data unit is added to a leaf node and in connection with a deletion the pointer pointing to the data unit is deleted from a leaf node,

a given maximum number of pointers that an individual node can contain is defined for the nodes, an individual node being full when it has said maximum number of pointers and non-full in other cases,

the additions to be made to said part are directed in the tree-shaped data structure to the first non-full node, seen from below, on a predetermined first edge of the data structure and they are further implemented in such a way that the leaf nodes remain at the same hierarchy level of the tree-shaped data structure, wherein when a non-full node is not present, new nodes are created to keep the leaf nodes at the same hierarchy level, and

the deletions to be made from said part are directed to the leaf node on the predetermined other edge of the tree.

2. A method as claimed in claim 1, characterized in that the deletions are directed to the leaf node that is on the opposite edge of the tree in relation to the node to which the additions are directed.

3. A method as claimed in claim 1, characterized in that if upon deletion an internal node is emptied of pointers, the deletion proceeds in the data structure upwards from said node in accordance with the pointers, and if it is found that the root node of the structure contains only one pointer, the root node is deleted and the node to which said pointer points is made the new root node of the data structure.

4. A method as claimed in claim 1, characterized in that in addition to the tree-shaped structure, the memory employs a separate header node (HN) comprising three elements each of which may be empty or contain a pointer, so that when one element contains a pointer it points to a separate node constituting the end of the queue, when a given second element contains a pointer it points to said tree-shaped data structure, and when a given third element contains a pointer it points to a separate node constituting the beginning of the queue.

5. A method as claimed in claim 4, characterized in that the header node employs an identifier (IB) indicating in each case which of said separate nodes constitutes the beginning and which the end of the queue.

6. A method as claimed in claim 4, characterized in that the additions are carried out in such a way that the node constituting the end of the queue is first filled with pointers, whereafter the node is added as a leaf node to said tree-shaped structure.

7. A method as claimed in claim 4, characterized in that the deletions are carried out in such a way that when said third element contains a pointer the deletion is made from the node pointed to by said pointer and when said third element is empty the deletion is made from said tree-shaped structure by deleting an entire leaf node therefrom and making the part remaining in said leaf node after the deletion the node constituting the beginning of the queue.

8. A method for implementing a queue in a memory (MEM) in which data is stored as data units for each of which a dedicated memory space is assigned in the memory, in accordance with which method data units are added to and deleted from the memory,

characterized in that

at least part of the queue is implemented as a tree-shaped data structure known per se, having nodes at several different hierarchy levels, wherein an individual node can be (i) an internal node containing at least one pointer pointing to a node lower in the tree-shaped hierarchy or (ii) a leaf node containing at least one data unit, wherein the node at the highest level of the structure is the root node of the structure and wherein the data unit is added to and deleted from a leaf node,

a given maximum number of pointers for the internal nodes and a given maximum number of data units for the leaf nodes that an individual node can contain is defined, an individual node being full when it has said maximum number of pointers or data units and non-full in other cases,

the additions to be made to said part are directed in the tree-shaped data structure to the first non-full node, seen from below, on a predetermined first edge of the data structure and they are further implemented in such a way that the leaf nodes remain at the same hierarchy level of the tree-shaped data structure, wherein when a non-full node is not present, new nodes are created to keep the leaf nodes at the same hierarchy level, and

the deletions to be made from said part are directed to the leaf node on the predetermined other edge of the tree.

9. A method as claimed in claim 8, characterized in that the deletions are directed to the leaf node that is on the opposite edge of the tree in relation to the node to which the additions are directed.

10. A method as claimed in claim 8, characterized in that if upon deletion an internal node is emptied of pointers, the deletion proceeds in the data structure upwards from said node in accordance with the pointers, and if it is found that the root node of the structure contains only one pointer, the root node is deleted and the node to which said pointer points is made the new root node of the data structure.

11. A method as claimed in claim 8, characterized in that in addition to the tree-shaped structure, the memory employs a separate header node (HN) comprising three elements each of which may be empty or contain a pointer, so that when one element contains a pointer it points to a separate node constituting the end of the queue, when a given second element contains a pointer it points to said tree-shaped data structure, and when a given third element contains a pointer it points to a separate node constituting the beginning of the queue.

12. A method as claimed in claim 11, characterized in that the header node employs an identifier (IB) indicating in each case which of said separate nodes constitutes the beginning and which the end of the queue.

13. A method as claimed in claim 11, characterized in that the additions are carried out in such a way that the node constituting the end of the queue is first filled with data units, whereafter the node is added as a leaf node to said tree-shaped structure.

14. A method as claimed in claim 11, characterized in that the deletions are carried out in such a way that when said third element contains a pointer the deletion is made from the node pointed to by said pointer and when said third element is empty the deletion is made from said tree-shaped structure by deleting an entire leaf node therefrom and making the part remaining in said leaf node after the deletion the node constituting the beginning of the queue.

15. A memory arrangement for implementing a queue, said queue comprising memory units stored in the memory and said arrangement including

a tree-shaped data structure stored in the memory, having nodes at several different hierarchy levels, wherein an individual node can be (i) an internal node containing at least one pointer pointing to a node lower in the tree-shaped hierarchy or (ii) a leaf node containing at least one pointer to a data unit stored in the memory or at least one data unit, the node at the highest level of the structure being the root node of the structure,

characterized in that

each node contains at most a given predetermined maximum number of pointers or data units, a node being full when it has said maximum number of pointers or data units, and that

all nodes of the tree-shaped data structure are full except for the nodes on the edges of the structure, and that

all leaf nodes of the tree-shaped data structure are continually at the same hierarchy level, wherein the pointers or data units contained in the leaf nodes form at least part of the queue.

16. A memory arrangement as claimed in claim 15, characterized in that it further comprises a separate header node (HN) comprising three elements each of which may be empty or contain a pointer, so that when one element contains a pointer it points to a separate node constituting the end of the queue, when a given second element contains a pointer it points to said tree-shaped data structure, and when a given third element contains a pointer it points to a separate node constituting the beginning of the queue, wherein the tree-shaped data structure forms at least the middle part of the queue.

17. A memory arrangement as claimed in claim 16, characterized in that the header node further comprises an identifier (IB) indicating the nodes constituting the beginning and the end of the queue in each case.