Electrical computers and digital processing systems: memory – Storage accessing and control – Memory configuring
Reexamination Certificate
2001-03-02
2002-04-16
Elmore, Reba I. (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Memory configuring
C711S165000
Reexamination Certificate
active
06374339
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to the implementation of a memory. More specifically, the invention relates to the implementation of a queue, particularly a FIFO-type queue (First In First Out), in a memory. The solution in accordance with the invention is intended for use specifically in connection with functional memories. By a functional memory is understood a memory in which updates, such as additions, are carried out in such a way that first the path from the root of a tree-shaped structure to the point of updating is copied, and thereafter the update is made in the copied data (i.e., the update is not directly made to the existing data). Such an updating procedure is also termed “copy-on-write”.
BACKGROUND OF THE INVENTION
In overwrite memory environments, in which updates are not made in the copy but directly in the original data (overwrite), a FIFO queue is normally implemented by means of a double-ended list of the kind shown in FIG.
1
. The list comprises nodes of three successive elements in a queue, three of such successive nodes being shown in the figure (references N(i−1), Ni and N(i+1)). The element on the first edge of each node has a pointer to the preceding node in the queue, the element on the opposite edge again has a pointer to the next node in the queue, and the middle element in the node has either the actual stored data record or a pointer to a record (the figure shows a pointer).
However, such a typical way of implementing a FIFO queue is quite ineffective for example in connection with functional memories, since each update would result in copying of the entire queue. If, therefore, the queue has e.g. N nodes, all N nodes must be copied in connection with each update prior to performing the update.
SUMMARY OF THE INVENTION
It is an object of the present invention to accomplish an improvement to the above drawback by providing a novel way of establishing a queue, by means of which the memory can be implemented in such a way that the amount of required copying can be reduced in a functional structure as well. This objective is achieved with a method as defined in the independent claims.
The idea of the invention is to implement and maintain a queue by means of a tree-shaped structure in which the nodes have a given maximum size and in which (1) additions of data units (to the queue) are directed in the tree-shaped data structure to the first non-full node, seen from below, on the first edge of the data structure and (2) deletions of data units (from the queue) are also directed to a leaf node on the edge of the tree, typically on the opposite edge. Furthermore, the idea is to implement the additions in such a way that the leaf nodes remain at the same hierarchy level of the tree-shaped data structure, which means that when such a non-full node is not present, new nodes are created to keep the leaf nodes at the same hierarchy level. The tree-shaped data structure will also be termed shortly a tree in the following.
When the solution in accordance with the invention is used, each update to be made in the functional environment requires a time and space that are logarithmically dependent on the length of the queue, since only the path leading from the root to the point of updating must be copied from the structure. The length of this path increases logarithmically in relation to the length of the queue. (When a FIFO queue contains N nodes, log N nodes shall be copied, where the base number of the logarithm is dependent on the maximum size of the node.)
Furthermore, in the solution in accordance with the invention the node to be updated is easy to access, since the search proceeds by following the edge of the tree until a leaf node is found. This leaf node provides the point of updating.
In accordance with a preferred embodiment of the invention, the data structure also comprises a separate header node 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 structure that is maintained in the above-described manner, and when a given third element contains a pointer it points to a separate node constituting the beginning of the queue. In this structure, additions are made in such a way that the node constituting the end is always filled first, and only thereafter will an addition be made to the tree-shaped structure. Correspondingly, an entire leaf node at a time is always deleted from the tree-shaped structure, and said leaf node is made to be the node constituting the beginning of the queue, wherefrom deletions are made as long as said node has pointers or data units left. Thereafter, a deletion is again made from the tree. On account of such a solution, the tree need not be updated in connection with every addition or deletion. In this way, the updates are made faster than heretofore and require less memory space than previously.
Since the queue in accordance with the invention is symmetrical, it can be inverted in constant time and constant space irrespective of the length of the queue. In accordance with another preferred additional embodiment of the invention, the header node makes use of an identifier indicating in each case which of said separate nodes constitutes the beginning and which constitutes the end of the queue. The identifier thus indicates which way the queue is interpreted in each case. The queue can be inverted by changing the value of the identifier, and the tree structure will be interpreted as a mirror image.
REFERENCES:
patent: 4320455 (1982-03-01), Woods et al.
patent: 5432908 (1995-07-01), Heddes et al.
patent: 5671446 (1997-09-01), Rakity et al.
patent: 5848416 (1998-12-01), Tikkanen
patent: 6032207 (2000-02-01), Wilson
patent: 6115716 (2000-09-01), Tikkanen et al.
patent: 2001/0042186 (2001-11-01), Ilvonen et al.
patent: 0650131 (1995-04-01), None
patent: 0717347 (1996-06-01), None
patent: 2012084 (1979-07-01), None
patent: WO 95/34155 (1995-12-01), None
Altera Law Group LLC
Elmore Reba I.
Nokia Networks Oy
LandOfFree
Method for implementing a queue in a memory, and memory... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for implementing a queue in a memory, and memory..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for implementing a queue in a memory, and memory... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2856763