US6049802A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for generating a linked list in a computer memory
Assignee: Lockheed Martin Corp
•
Filing: 1994-06-27
•
Granted: 2000-04-11
•
Expires: 2014-06-27
Abstract
Abstract A system and method for storing data in a linked list memory architecture maintains several key list parameters. When data to be stored is received, a memory manager determines the list in which the data belongs and retrieves several of the parameters. The parameters retrieved indicate the address of the current location at which the received data is to be stored and the address of the next location that is to be linked to the current list. The memory manager writes the data to the current location pointed to by the first address and writes the second address into a pointer field in that current location. Because the address of the next location in the list is determined before data is written to the current location, this next address can be written in the same cycle in which the data is written.
Inventors
- 👤 William N. Waggener, Jr.
- 👤 Thomas Albert Bray
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 17:19
CPC Classifications
G; G06; G06F; G06F5/00; G06F5/06; G06F5/065; G06F2205/00; G06F2205/06; G06F2205/064
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
119 words
A method for storing data in a memory having a plurality of linked lists and a free list, comprising the steps of: (a) determining one of the plurality of linked lists in which data is to be stored; (b) determining a next available address for said linked list determined in said step (a), wherein said next available address points to a current location at which the data is to be stored for said linked list; (c) determining a free list start address, wherein said free list start address indicates an address of an available location in the free list; and (d) writing the data and said free list start address to said current location in a single write cycle.
Claim 2
Independent Claim
119 words
A method for storing data in a memory having a plurality of linked lists and a free list, comprising the steps of: (a) determining one of the plurality of linked lists in which data is to be stored; (b) determining a next available address for said linked list determined in said step (a), wherein said next available address points to a current location at which the data is to be stored for said linked list; (c) determining a free list start address, wherein said free list start address indicates an address of an available location in the free list; and (d) writing the data and said free list start address to said current location in a single write cycle.
Claim 3
Dependent Claim
41 words
The method of claim 1, wherein said steps (b) and (c) of determining said next available address and said free list start address comprise the steps of retrieving said next available address and said free list start address from a table.
Claim 4
Dependent Claim
49 words
The method of claim 2, further comprising the steps, after said step (d) of: (e) storing in said table said free list start address determined in said step (c) as said next available address for said linked list; and (f) incrementing said free list start address in said table.
Claim 5
Dependent Claim
56 words
The method of claim 2, further comprising the steps, after said step (d) of: (e) storing in said table said free list start address determined in said step (c) as said next available address for said linked list; and (f) storing in said table a pointer from said available location as said free list start address.
Claim 6
Dependent Claim
28 words
The method of claim 1, further comprising a step (e) of linking a now-available location to the free list after data has been read from said now-available location.
Claim 7
Dependent Claim
57 words
The method of claim 5, wherein said step (e) comprises the steps of: (f) determining a free list end address, wherein said free list end address indicates the address of a last location in the free list that is available for storing data; (g) updating a pointer in said last location to point to said now-available location.
Claim 8
Dependent Claim
29 words
The method of claim 6, wherein said step (e) further comprises the step (h) of updating said free list end address to indicate the address of said now-available location.
Claim 9
Independent Claim
128 words
A system for storing data in one of a plurality of linked lists, comprising: a memory having a plurality of linked lists and a free list; first means for determining one of the plurality of linked lists in which data is to be stored; second means for determining a next available address for said linked list, wherein said next available address indicates a current location in said memory at which the data is to be stored for said linked list; third means for determining a free list start address, wherein said free list start address indicates an address of an available location in the free list; and fourth means for writing the data and said free list start address to said current location in a single write cycle.
Claim 10
Independent Claim
128 words
A system for storing data in one of a plurality of linked lists, comprising: a memory having a plurality of linked lists and a free list; first means for determining one of the plurality of linked lists in which data is to be stored; second means for determining a next available address for said linked list, wherein said next available address indicates a current location in said memory at which the data is to be stored for said linked list; third means for determining a free list start address, wherein said free list start address indicates an address of an available location in the free list; and fourth means for writing the data and said free list start address to said current location in a single write cycle.
Claim 11
Dependent Claim
37 words
The system of claim 8, wherein said means for determining said next available address and said free list start address comprises means for retrieving said next available address and said free list start address from a table.
Claim 12
Dependent Claim
44 words
The system of claim 9, further comprising: means for storing in said table said free list start address determined by said third means as said next available address for said linked list; and means for incrementing said free list start address in said table.
Claim 13
Dependent Claim
51 words
The system of claim 9, further comprising: means for storing in said table said free list start address determined by said third means as said next available address for said linked list; and means for storing in said table a pointer from said available location as said free list start address.
Claim 14
Dependent Claim
30 words
The system of claim 8, wherein said memory manager further comprises means for linking a now-available location to the free list after data has been read from said now-available location.
Claim 15
Dependent Claim
61 words
The system of claim 12, wherein said means for linking said now-available location comprises: means for determining a free list end address, wherein said free list end address indicates the address of a last location in the free list that is available for storing data; and means for updating a pointer in said last location to point to said now-available location.
Claim 16
Dependent Claim
30 words
The system of claim 12, wherein said means for linking said now-available location comprises means for updating said free list end address to indicate the address of said now-available location.
Claim 17
Dependent Claim
123 words
A memory system for storing data in a memory having a plurality of memory locations linked together in one or more linked lists, comprising: table means for storing list parameters, wherein said list parameters comprise a next available address for each of the linked lists, and a free list start address; and memory manager means, comprising means for determining in which of the linked lists the data is to be stored, means for retrieving said next available address for said linked list in which the data is to be stored and for retrieving said free list start address, and means for writing in a single cycle the data and said free list start address to the location indicated by said next available address.
Claim 18
Dependent Claim
123 words
A memory system for storing data in a memory having a plurality of memory locations linked together in one or more linked lists, comprising: table means for storing list parameters, wherein said list parameters comprise a next available address for each of the linked lists, and a free list start address; and memory manager means, comprising means for determining in which of the linked lists the data is to be stored, means for retrieving said next available address for said linked list in which the data is to be stored and for retrieving said free list start address, and means for writing in a single cycle the data and said free list start address to the location indicated by said next available address.
Claim 19
Dependent Claim
63 words
The memory system of claim 15, wherein said memory manager further comprises: means for storing said free list start address as said next available address after said data and free list start address are written to said location; and means for updating said free list start address in said table to indicate the address of a next available location in the free list.
Claim 20
Dependent Claim
31 words
The memory system of claim 15, wherein said memory manager further comprises means for linking a now-available location to the free list after data has been read from said now-available location.
Claim 21
Dependent Claim
62 words
The memory system of claim 17, wherein said means for linking said now-available location comprises: means for determining a free list end address, wherein said free list end address indicates the address of a last location in the free list that is available for storing data; and means for updating a pointer in said last location to point to said now-available location.
Claim 22
Dependent Claim
31 words
The memory system of claim 18, wherein said means for linking said now-available location comprises means for updating said free list end address to indicate the address of said now-available location.
Claim 23
Independent Claim
141 words
A method for storing data in a memory having a plurality of linked lists and a free list, comprising the steps of: (a) determining a next available address for each said linked list, wherein said next available address points to a location at which data is to be stored for a corresponding linked list; (b) determining a free list start address, wherein said free list start address indicates an address of an available location in the free list that has not been designated as said next available address for any one of the plurality of linked lists, wherein said free list start address becomes a new next available address for a linked list that has been written to; and (c) writing the data and said free list start address to one of said next available addresses in a single write cycle.
Claim 24
Independent Claim
141 words
A method for storing data in a memory having a plurality of linked lists and a free list, comprising the steps of: (a) determining a next available address for each said linked list, wherein said next available address points to a location at which data is to be stored for a corresponding linked list; (b) determining a free list start address, wherein said free list start address indicates an address of an available location in the free list that has not been designated as said next available address for any one of the plurality of linked lists, wherein said free list start address becomes a new next available address for a linked list that has been written to; and (c) writing the data and said free list start address to one of said next available addresses in a single write cycle.
References Cited (Backward Citations)
US5226147A
Cited
EP0378195A2
Cited
US5210744A
Cited
US5293346A
Cited
US5301296A
Cited
EP0522224A1
Cited
US5359568A
Cited
US5303302A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-04-11 | 2003-10-11 | 2004-04-11 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-04-11 | 2007-10-11 | 2008-04-11 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-04-11 | 2011-10-11 | 2012-04-11 | $7700.00 | Window Closed / Lapsed |