Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-09-21
2003-11-04
Rones, Charles (Department: 2175)
Data processing: database and file management or data structures
Database design
Data structure types
C711S132000
Reexamination Certificate
active
06643662
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention is related generally to an improved data processing system and, more particularly, to an improved first in last out data structure within a memory array.
2. Description of Related Art
A stack or First In Last Out (FILO) data structure is used in many computer applications. Often multiple stacks are needed in a single application and they are added on an as needed basis because, at the beginning of the application, it is not known how many stacks will be needed. Since memory in computer systems is arranged as a linear array, the application will have some segment of this linear array that it will use to place multiple stacks. The way stacks are traditionally implemented is with a base and head pointer.
In a typical case, two stacks are placed at opposite ends of the memory array. One stack grows to the right and the other stack grows to the left. Each stack may grow until it hits the stack coming from the opposite direction (which is referred to as a collision).
The arrangement with two stack growing toward one another from opposite ends of the array is efficient if both the stacks grow at the same rate. That is, all memory within the memory array will be consumed before a collision. However, if a third stack is needed, a problem may arise. If all three stacks grow at the same rate, and the third stack grows in only one direction, and the third stack is placed in the middle of the first two stacks, then the third stack will tend to collide with one of the other two stacks, before the other of the other two stacks has used all its space. The third stack could be offset in location from the center in an effort to anticipate this problem, but if the three stacks do not grow at the same rate, then the selected offset location of the third stack may not help, and may even aggravate the problem.
In one of the related applications, these problems are addressed by one or more bi-directionally growing stacks. The bi-directionally growing stacks are useful for addressing problems which arise in managing the space in a linear memory array, including allocation of the space. However, a need exists for a method or apparatus to manage memory having other features, which relate to aspects of these problems in a different way, and which may provide even greater adaptability in certain circumstances.
SUMMARY OF THE INVENTION
The present invention addresses this need in a method, system, and apparatus for managing storage of data elements. A storage area, having a first and second end, is provided for storing the data elements. In the storage area, a first stack of data elements has first and second ends respectively facing the first and second ends of the storage area, and a second stack has data elements located proximate both ends of the first stack. That is, the second stack is split, with the first stack interposed between data elements of the second stack. Likewise, there may be a third and fourth stack, and so on, which are split into more than one part. The stacks increase in size toward both the first end of the storage area and the second end of the storage area, responsive to the storing of successive ones of the data elements in the respective stacks. Furthermore, the increasing in size of one of the split stacks may include increasing away from the first stack, or alternatively, increasing toward the first stack.
In still another aspect, the storage area has four mutually exclusive sections. The first section (an “end” one of the sections) has an end proximate one of the storage area ends. The second section (another “end” one of the sections) has an end proximate a second one of the storage area ends. A third section (a “middle” section) is located between the first and second sections. A fourth section (another “middle” section) is also located between the first and second sections. The first stack is confined to the two middle sections and the second stack to the two end sections.
In yet another aspect the split third stack is confined to the middle two sections.
Regarding the aspect wherein stacks, such as the second and third stack, increase in size toward both the first and second ends of the storage area, in one embodiment the second stack increases away from the first stack, and the third stack increases toward the first stack. Alternatively, the second stack increases toward the first stack, and the third stack increases away from the first stack.
As described in one of the related applications, it is an advantage of bi-directionally growing stacks that under certain conditions and within certain limitations a storage area is more efficiently used by an odd number of bi-directional stacks than by an odd number of unidirectional stacks. It is an advantage of the present invention that space in the storage area is used more efficiently, under certain conditions and within certain limitations, by having a first bi-directional stack located in a central part of the storage area, and splitting a second bi-directional stack into two parts, one on either side of the first stack.
REFERENCES:
patent: 6006323 (1999-12-01), Ma et al.
patent: 6138210 (2000-10-01), Tremblay et al.
Kaiping Li et al., “A Bidirectional multiple stack algorithm” IEEE trasactions on communications, vol, 47, No. 1, Jan. 1999.*
Korsh et al., “A Multiple Stack Manipulation Procedure,” Nov. '83, pp 27-29, plus one page w/ ltr.
Knuth, “The Art of Computer Programming,” 2d ed., vol. 1, pp240-248.
Garwick, “Data Storage in Compilers,” Bit 4, 1964, pp 137-140.
Yeh et al., Dynamic Initial Allocation and Local Reallocation Procedures for Multiple Stacks, Communications of the ACM, Feb. '86, pp 30-39.
Farago Steven Robert
Wright Kenneth Lee
England Anthony V. S.
International Business Machines - Corporation
Rones Charles
Salys Casimer K.
Wu Yicun
LandOfFree
Split bi-directional stack in a linear memory array does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Split bi-directional stack in a linear memory array, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Split bi-directional stack in a linear memory array will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3169160