Electrical computers and digital processing systems: memory – Storage accessing and control – Control technique
Reexamination Certificate
2001-12-10
2004-05-25
Sparks, Donald (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Control technique
C711S147000, C711S165000, C711S159000, C711S133000, C711S170000
Reexamination Certificate
active
06742091
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to implementing a double-ended queue in a memory arrangement. The double-ended queue, also called a deque, is in a way a combination of a queue and a stack, to which elements can be added and from which they can be removed as in a queue and a stack. The solution according to the invention is intended for use particularly in connection with functional memories. Functional memories are memories where updates such as additions are carried out by first copying the path from the root of the tree-like structure to the point to be updated, and updating is then carried out on the copied data (i.e. updating is not carried out directly on the existing data). Such a update method is also called “copy-on-write”.
TECHNICAL BACKGROUND OF THE INVENTION
In overwriting memory environments where updating is not carried out on a copy but on the original data instead (by overwriting), a FIFO (First In First Out) queue, for instance, is implemented using a double-ended list similar to the one shown in FIG.
1
. The list consists of three-element nodes in a queue; three such successive nodes are shown in the figure (references N(i−1), Ni and N(i+1)). The elements on the first edge of each node have a pointer to the previous node in the queue, whereas the element on the opposite edge has a pointer to the node next in the queue, and the element in the middle of the node either has the actual stored record or a pointer to the record (the figure shows a pointer).
Such typical implementation of a FIFO queue is, however, rather inefficient e.g. in connection with functional memories, because each update would require copying the entire queue. Therefore, if the queue has for example N nodes, in connection with each update all N nodes have to be copied before carrying out the update operation.
A double-ended queue, however, is a queue where an element can be added to either end or removed from either end. In imperative (overwriting) environments, a double-ended queue can be implemented or realised e.g. as a double-ended linked list. In functional environments, the conventional method is to divide the queue into two lists, the head list and the tail list. The tail list is stored in the memory in reverse order, i.e. the element stored last in the queue is the first element in the tail. Elements are removed from the queue by fetching them up from the head end. If the head list becomes empty, the tail list is turned into a new head list. The amount of processing involved with additions and deductions on such a list is on average constant. In the worst case scenario, however, the amount of processing is linear, meaning that the processing time will increase directly proportional to the amount of data.
When developing new functional memory structures, one should aim at structures which minimise the amount of processing due to memory rupdates. Another important factor is the required memory space which one should try to minimise.
SUMMARY OF THE INVENTION
The objective of the invention is to create a new type of implementation for a double-ended queue, with which the memory in a functional structure can be implemented in such a way that the amount of processing required by memoryupdates, such as copying due to additions, is minimised and also the requirement for memory space is significantly reduced. The set objective is achieved with the method shown in the independent patent claims.
The idea behind the invention is to implement the double-ended queue as a hierarchic data structure consisting of buffers, where the buffers forming the front and tail ends of the queue are at the highest hierarchy level of the structure and where the middle of the queue consists of buffers on adjacent levels of hierarchy in such a way that the elements of a certain level of hierarchy are buffers containing elements of the next higher level of hierarchy (which can in turn be buffers containing elements of the next higher level of hierarchy, etc.). Additions made to the queue and removals from it are always targeted at the buffers forming the front or tail end of the queue. When the buffer in question becomes full as a result of the addition, it is moved to the next lower level of hierarchy as an element of a node (also known as a buffer) on that level, and when the buffer in question becomes empty, a full buffer is fetched up from the next lower level of hierarchy. The elements of the buffers on different levels of the hierarchy, therefore, differ from each other in such a way that if the elements of the buffer on the first level are e.g. integers, then the elements of the buffers on the second level are buffers which contain integers, the buffers on the third level are buffers which contain buffers which contain integers, etc. In other words, additions are made by first filling the buffer forming the front or tail end of the queue and only then moving the full buffer from the subject level to the lower level. Likewise, when removing elements, an empty buffer is replaced by fetching up from the lower level an element which, when brought to the target level, is a buffer filled with elements of the target level.
Each full buffer on different levels of hierarchy contains the same, predetermined number of elements. In other words, a certain maximum has been defined for the number of elements in a buffer. The buffers are always full, with the exception of those forming the front and tail ends of the queue and the top node of each level of hierarchy, the so-called root node, which can be either a full or non-full buffer. However, a buffer can not contain a non-full buffer, because only full buffers are moved from the highest level of hierarchy to the middle of the queue. The queue will not contain any empty buffers either, as empty buffers are replaced with new full ones.
The first full buffer of each level of hierarchy in a data structure forming a queue is transformed into a separate three-field node, a 3-tuple, when a buffer is added (at the highest level) or moved when adding (at lower levels) from a higher level of hierarchy. In this case, the said full buffer is moved to the end of the 3-tuple, and the new buffer formed for the added element or moved buffer is moved to the tail of the 3-tuple. The middle of the 3-tuple is empty to start with, whereas the head and tail of the 3-tuple can never be empty.
Using the above technique, full buffers are moved from one level to another on all levels of hierarchy.
Elements can be added either as the first element of the buffer forming the front end of the queue or, alternatively, as the last element of the buffer forming the tail end of the queue. Similarly, removing is done either by removing the first element of the buffer forming the front end of the queue or, alternatively, the last element of the buffer forming the tail end of the queue. In other words, both the FIFO (First In First Out) and LIFO (Last In First Out) queue disciplines apply in the queue.
When using a solution according to the invention, the operations on the trees of the data structure are primarily carried out at the head or tail of the first level of hierarchy, and the probability for having to visit lower levels of hierarchy with the operation reduces exponentially as we go down the data structure. Due to this, the need to use memory space is reduced and updates are quicker. The time taken for adding and removing elements is, as a rule, constant.
REFERENCES:
patent: 4320455 (1982-03-01), Woods et al.
patent: 5224215 (1993-06-01), Disbrow
patent: 5442763 (1995-08-01), Bartfai et al.
patent: 5555396 (1996-09-01), Alferness et al.
patent: 5801572 (1998-09-01), Nakamura
patent: 5906658 (1999-05-01), Raz
patent: 5995967 (1999-11-01), Iacobovici et al.
patent: 6374339 (2002-04-01), Iivonen
patent: 0717347 (1996-06-01), None
Schneider et al., “Concepts in Data Structures and Software Development”, © 1991, West Publishing Company, pp. 84-91.*
Kruse et al., “Data Structures and Program Design in C”, © 1991, Prentice-Hall, Inc., pp. 94 and 106-119.*
“Diamond deque: A simp
Nokia Corporation
Peugh Brian R.
Sparks Donald
Squire Sanders & Dempsey L.L.P.
LandOfFree
Method of implementing a double-ended queue in a memory and... 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 of implementing a double-ended queue in a memory and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of implementing a double-ended queue in a memory and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3217905