US5787447A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Memory allocation maintaining ordering across multiple heaps
Assignee: Sun Microsystems Inc
•
Filing: 1995-05-08
•
Granted: 1998-07-28
•
Expires: 2015-05-08
Abstract
Abstract A method and apparatus for adding and deleting data in a plurality of heaps stored in memory, where the ordering of the data in the heaps is maintained across the heaps as the additions and deletions are performed. Not all entries in the heaps have a corresponding entry in all of the other heaps, but the ordering of the data in the heaps is in accordance with an order dependent list stored in memory. Such ordered heaps are useful for example, in a incremental linker software program.
Inventors
- 👤 Neil G. Smithline
- 👤 Christopher D. Quenelle
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 17:11
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/40; G06F8/54; G06F12/00; G06F12/02; G06F12/0223; G06F12/023
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
68 words
An apparatus for manipulating entries in a plurality of heaps stored in a memory of a data processing system, comprising means for determining respective amounts of free space required in each of the plurality of heaps; and means for allocating the respective amounts of required free space in each of the plurality of heaps, so that an order of entries in the heaps remains ordered across the heaps.
Claim 2
Independent Claim
68 words
An apparatus for manipulating entries in a plurality of heaps stored in a memory of a data processing system, comprising means for determining respective amounts of free space required in each of the plurality of heaps; and means for allocating the respective amounts of required free space in each of the plurality of heaps, so that an order of entries in the heaps remains ordered across the heaps.
Claim 3
Dependent Claim
35 words
The apparatus of claim 1, further comprising: means for taking the allocated respective amounts of free space from respective free lists stored in the memory and associated with respective ones of the plurality of heaps.
Claim 4
Dependent Claim
31 words
The apparatus of claim 1, further comprising: means for deallocating respective amounts of space, wherein each deallocated amount of space is in a same relative ordering in the plurality of heaps.
Claim 5
Dependent Claim
31 words
The apparatus of claim 3, further including: means for returning the deallocated space to respective free lists stored in the memory and associated with respective ones of the plurality of heaps.
Claim 6
Independent Claim
68 words
An apparatus for manipulating entries in a plurality of heaps stored in a memory of a data processing system, comprising: means for determining respective amounts of free space required in each of the plurality of heaps; means for allocating the respective amounts of required free space in each of the plurality of heaps, so that a physical order of entries in the heaps remains ordered across the heaps.
Claim 7
Independent Claim
68 words
An apparatus for manipulating entries in a plurality of heaps stored in a memory of a data processing system, comprising: means for determining respective amounts of free space required in each of the plurality of heaps; means for allocating the respective amounts of required free space in each of the plurality of heaps, so that a physical order of entries in the heaps remains ordered across the heaps.
Claim 8
Dependent Claim
150 words
A computer program product comprising: A computer usable medium having computer readable code embodied therein for causing a finding and an ordering of a predetermined amount of free space in each of a plurality of heaps stored in a memory of a data processing system, the method comprising the steps, performed by the data processing system, the computer program product comprising: computer readable program code devices configured to cause a computer to effect receiving a plurality of predetermined values indicating a respective amount of space to be located in each of a plurality of heaps; computer readable program code devices configured to cause a computer to effect determining respective locations in the plurality of heaps having each respective amount of space; and computer readable program code devices configured to cause a computer to effect allocating the respective locations, wherein the allocated locations maintain an ordering across the plurality of heaps.
Claim 9
Dependent Claim
150 words
A computer program product comprising: A computer usable medium having computer readable code embodied therein for causing a finding and an ordering of a predetermined amount of free space in each of a plurality of heaps stored in a memory of a data processing system, the method comprising the steps, performed by the data processing system, the computer program product comprising: computer readable program code devices configured to cause a computer to effect receiving a plurality of predetermined values indicating a respective amount of space to be located in each of a plurality of heaps; computer readable program code devices configured to cause a computer to effect determining respective locations in the plurality of heaps having each respective amount of space; and computer readable program code devices configured to cause a computer to effect allocating the respective locations, wherein the allocated locations maintain an ordering across the plurality of heaps.
Claim 10
Independent Claim
247 words
A method for finding a predetermined amount of free space in each of a plurality of heaps stored in a memory of a data processing system, the method comprising the steps, performed by the data processing system, of: establishing a hi pointer and a lo pointer for each of the plurality of heaps, so that each heap has an associated lo pointer and an associated hi pointer; advancing at least one of the lo pointers to be equal to its corresponding hi pointer, wherein the advancing step includes the sub-step of advancing at least one of the lo pointers corresponding to at least one minimum hi pointer to be equal to its corresponding minimum hi pointer; advancing at least one of the corresponding hi pointers to point to a next significant segment in the plurality of heaps, wherein the advancing step includes the sub-step of advancing at least one of the corresponding minimum hi pointers to point to a next significant segment in the plurality of heaps; determining whether the predetermined amount of free space exists in each of the heaps between each associated lo pointer and associated hi pointer; and when the predetermined amount of free space is not found between all of the hi pointers and the lo pointers, keeping an existing value in the lo pointers associated with heaps that do not have a corresponding hi pointer, and keeping an existing value in the corresponding hi pointer that is not a minimum hi pointer.
Claim 11
Independent Claim
247 words
A method for finding a predetermined amount of free space in each of a plurality of heaps stored in a memory of a data processing system, the method comprising the steps, performed by the data processing system, of: establishing a hi pointer and a lo pointer for each of the plurality of heaps, so that each heap has an associated lo pointer and an associated hi pointer; advancing at least one of the lo pointers to be equal to its corresponding hi pointer, wherein the advancing step includes the sub-step of advancing at least one of the lo pointers corresponding to at least one minimum hi pointer to be equal to its corresponding minimum hi pointer; advancing at least one of the corresponding hi pointers to point to a next significant segment in the plurality of heaps, wherein the advancing step includes the sub-step of advancing at least one of the corresponding minimum hi pointers to point to a next significant segment in the plurality of heaps; determining whether the predetermined amount of free space exists in each of the heaps between each associated lo pointer and associated hi pointer; and when the predetermined amount of free space is not found between all of the hi pointers and the lo pointers, keeping an existing value in the lo pointers associated with heaps that do not have a corresponding hi pointer, and keeping an existing value in the corresponding hi pointer that is not a minimum hi pointer.
Claim 12
Dependent Claim
44 words
The method of claim 7, further comprising the step of: when the predetermined amount of free space is found between all of the hi pointers and the lo pointers, adding a segment to at least one of the heaps in the found free space.
Claim 13
Dependent Claim
39 words
The method of claim 7, further comprising the step of: repeating the establishing, advancing and determining steps until the predetermined amount of free space is found or until the associated hi pointers reach the end of their respective heaps.
Claim 14
Dependent Claim
56 words
The method of claim 7, further comprising the step of: advancing at least one of the hi pointers to point to a second significant segment in one of the plurality of heaps, wherein the second significant segment is at a higher location in its heap than the location of a first significant segment in its heap.
Claim 15
Dependent Claim
33 words
The method of claim 7, wherein a significant segment is a segment that has an entry pointing to the heap associated with a hi pointer and pointing to at least one other heap.
Claim 16
Dependent Claim
21 words
The method of claim 7, wherein free space in each of the plurality of heaps is connected in a linked list.
Claim 17
Dependent Claim
18 words
The method of claim 7, wherein the predetermined amount of free space is the same for each heap.
Claim 18
Dependent Claim
17 words
The method of claim 7, wherein the predetermined amount of free space is different for each heap.
Claim 19
Dependent Claim
54 words
The method of claim 14, wherein the determining step includes the steps of: checking each block of the free space between an associated lo pointer and associated hi pointer in ordering from largest to smallest; and using the first block of free space that is as large as the predetermined amount of free space.
Claim 20
Dependent Claim
54 words
The method of claim 14, wherein the determining step includes the steps of: checking each block of the free space between an associated lo pointer and associated hi pointer in ordering from largest to smallest; and using the largest block of free space that is as large as the predetermined amount of free space.
Claim 21
Dependent Claim
18 words
The method of claim 7, wherein at least two of the plurality of heaps are of different sizes.
Claim 22
Dependent Claim
42 words
The method of claim 7, further comprising the step of: receiving a sequence of inputs of the form: "alloc (V)" where "V" is a vector of integers, each representing the amount of space that needs to be allocated in a corresponding heap.
Claim 23
Dependent Claim
48 words
The method of claim 18, further comprising the step of: interspersing the sequence of inputs with commands of "free (i)" where "i" is a sequence number referring to the i'th alloc in the sequence of inputs and meaning that the memory associated with that "alloc" should be freed.
References Cited (Backward Citations)
US4757438A
Cited
US4920483A
Cited
US5222221A
Cited
US4989134A
Cited
US5088036A
Cited
US5182806A
Cited
US5325531A
Cited
US5321834A
Cited
US5301288A
Cited
US5535329A
Cited
US5355483A
Cited
WO1994002898A1
Cited
US5561786A
Cited
US5560003A
Cited
US5519866A
Cited
US5408650A
Cited
US5566321A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-07-27 | 2002-01-26 | 2002-07-28 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-07-27 | 2006-01-26 | 2006-07-28 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-07-27 | 2010-01-26 | 2010-07-28 | $7700.00 | Window Closed / Lapsed |