US5924098A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for managing a linked-list data structure
Assignee: Oracle America Inc
•
Filing: 1997-06-30
•
Granted: 1999-07-13
•
Expires: 2017-06-30
Abstract
Abstract A method of managing a linked-list data structure is disclosed. The linked-list data structure has a number of elements, each of which includes a data item and a pointer to a sequentially following element. The method allows the modification of the linked-list data structure, either by the insertion or removal of element therefrom, while permitting a concurrent and unsynchronized traversal operations with respect to the linked-list data structure. Specifically, the method requires that the pointers of elements within the linked-list data structure be modified using an atomic operation to reflect any modifications made to the linked-list data structure. The utilization of atomic operations to update the pointers ensures that the unsynchronized traversal operations examine a valid data path.
Inventors
- 👤 Kevin L Kluge
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 19:17
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/46; G06F9/52; G06F16/00; G06F16/90; G06F16/901; G06F16/9024; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99938
Claims Analysis
Total Claims: 29
Claim 1
Independent Claim
103 words
A computer-implemented method of managing a linked-list data structure, the linked-list data structure including a first element, the first element comprising a first data portion and a first pointer portion, the method including: modifying the linked-list data structure; updating the first pointer portion of the first element to reflect the modification to the linked-list data structure, the step of updating comprising an atomic operation; and performing a first unsynchronized traversal of the linked-list data structure concurrently with the modification of the linked-list data structure, the first unsynchronized traversal comprising a mark and sweep garbage collection operation with respect to the linked-list data structure.
Claim 2
Dependent Claim
103 words
A computer-implemented method of managing a linked-list data structure, the linked-list data structure including a first element, the first element comprising a first data portion and a first pointer portion, the method including: modifying the linked-list data structure; updating the first pointer portion of the first element to reflect the modification to the linked-list data structure, the step of updating comprising an atomic operation; and performing a first unsynchronized traversal of the linked-list data structure concurrently with the modification of the linked-list data structure, the first unsynchronized traversal comprising a mark and sweep garbage collection operation with respect to the linked-list data structure.
Claim 3
Dependent Claim
19 words
The computer-implemented method of claim 1 including performing concurrently a plurality of unsynchronized traversals of the linked-list data structure.
Claim 4
Dependent Claim
58 words
The computer-implemented method of claim 1 wherein the modification of the linked-list data structure comprises adding a second element into the linked-list data structure, the second element having a second data portion and a second pointer portion, and wherein the atomic operation includes modifying the first pointer portion of the first element to point to the second element.
Claim 5
Dependent Claim
26 words
The computer-implemented method of claim 3 wherein the atomic operation includes modifying the second pointer portion of the second element to point to a third element.
Claim 6
Dependent Claim
50 words
The computer-implemented method of claim 1 wherein the modification of the linked-list data structure comprises removing a second element from the linked-list data structure, and wherein the atomic operation includes modifying the first pointer portion of the first element to point to a third element instead of the second element.
Claim 7
Dependent Claim
18 words
The computer-implemented method of claim 1 wherein the modification of the linked-list data structure is a synchronous operation.
Claim 8
Dependent Claim
47 words
The computer-implemented method of claim 1 including performing a second unsynchronized traversal of the linked-list data structure concurrently with the modification of the linked-list data structure, the second unsynchronized traversal comprising a retrieval operation to retrieve a data portion of an element within the linked-list data structure.
Claim 9
Dependent Claim
128 words
In an object-oriented programming environment, a linked-list object comprising: a linked-list data structure including a plurality of elements, each element having a respective data portion and a pointer portion; a modifying method for modifying the linked-list data structure by the insertion or removal of a first element; an updating method for updating the pointer portion of a second element to reflect the modification to the linked-list data structure utilizing an atomic modify operation; and a traversal method for performing an unsynchronized traversal of the linked-list data structure concurrently with the modification of the linked-list data structure by the modifying method, the traversal method comprising a mark and sweep garbage collection method for performing an unsynchronized mark and sweep garbage collection operation with respect to the linked-list data structure.
Claim 10
Dependent Claim
128 words
In an object-oriented programming environment, a linked-list object comprising: a linked-list data structure including a plurality of elements, each element having a respective data portion and a pointer portion; a modifying method for modifying the linked-list data structure by the insertion or removal of a first element; an updating method for updating the pointer portion of a second element to reflect the modification to the linked-list data structure utilizing an atomic modify operation; and a traversal method for performing an unsynchronized traversal of the linked-list data structure concurrently with the modification of the linked-list data structure by the modifying method, the traversal method comprising a mark and sweep garbage collection method for performing an unsynchronized mark and sweep garbage collection operation with respect to the linked-list data structure.
Claim 11
Dependent Claim
135 words
A machine-readable medium including a sequence of instructions which, when executed by a machine, cause the machine to perform the steps of: modifying a linked-list data structure, the linked-list data structure including a first element, the first element having a first data portion and a first pointer portion, by the insertion or removal of a second element, the second element having a second data portion and a second pointer portion; updating the first pointer portion of the first element to reflect the modification to the linked-list data structure, the step of updating comprising an atomic operation; and performing a first unsynchronized traversal of the linked-list data structure concurrently with the modification of the linked-list data structure, the first unsynchronized traversal comprising a mark and sweep garbage collection operation with respect to the linked-list data structure.
Claim 12
Dependent Claim
135 words
A machine-readable medium including a sequence of instructions which, when executed by a machine, cause the machine to perform the steps of: modifying a linked-list data structure, the linked-list data structure including a first element, the first element having a first data portion and a first pointer portion, by the insertion or removal of a second element, the second element having a second data portion and a second pointer portion; updating the first pointer portion of the first element to reflect the modification to the linked-list data structure, the step of updating comprising an atomic operation; and performing a first unsynchronized traversal of the linked-list data structure concurrently with the modification of the linked-list data structure, the first unsynchronized traversal comprising a mark and sweep garbage collection operation with respect to the linked-list data structure.
Claim 13
Dependent Claim
30 words
The machine-readable medium of claim 9 including the step of performing a plurality of unsynchronized traversals of the linked-list data structure concurrently with the modification of the linked-list data structure.
Claim 14
Dependent Claim
42 words
The machine-readable medium of claim 9 wherein the step of modifying comprises adding the second element into the linked-list data structure, and wherein the atomic operation includes modifying the first pointer portion of the first element to point to the second element.
Claim 15
Dependent Claim
26 words
The machine-readable medium of claim 11 wherein the atomic operation includes modifying the second pointer portion of the second element to point to a third element.
Claim 16
Dependent Claim
51 words
The machine-readable medium of claim 9 wherein the step of modifying comprises removing the second element from the linked-list data structure, and the step of updating comprises the step of atomically modifying the first pointer portion of the first element to point to a third element instead of the second element.
Claim 17
Dependent Claim
19 words
The machine-readable medium of claim 9 wherein the step of modifying the linked-list data structure is a synchronous operation.
Claim 18
Dependent Claim
85 words
A computer-implemented method of managing a linked-list data structure, the linked-list data structure including an element comprising a data portion and a pointer portion, the method comprising: performing a first operation with respect to the linked-list data structure; and performing an unsynchronized traversal, comprising a mark and sweep garbage collection operation, of the linked-list data structure concurrently with the first operation, wherein the unsynchronized traversal includes performing a read of the pointer portion of the element, and the read is performed as an atomic operation.
Claim 19
Dependent Claim
85 words
A computer-implemented method of managing a linked-list data structure, the linked-list data structure including an element comprising a data portion and a pointer portion, the method comprising: performing a first operation with respect to the linked-list data structure; and performing an unsynchronized traversal, comprising a mark and sweep garbage collection operation, of the linked-list data structure concurrently with the first operation, wherein the unsynchronized traversal includes performing a read of the pointer portion of the element, and the read is performed as an atomic operation.
Claim 20
Dependent Claim
20 words
The computer-implemented method of claim 15 wherein the first operation is a further unsynchronized traversal of the linked-list data structure.
Claim 21
Dependent Claim
20 words
The computer-implemented method of claim 15 wherein the first operation is a further synchronized modification of the linked-list data structure.
Claim 22
Dependent Claim
92 words
A machine-readable medium comprising instructions which, when executed by a machine, cause the machine to perform the steps of: performing a first operation with respect to the linked-list data structure, the linked-list data structure including an element having a data portion and a pointer portion; and performing an unsynchronized traversal, comprising a mark and sweep garbage collection operation, of the linked-list data structure concurrently with the first operation; wherein the unsynchronized traversal includes performing a read of the pointer portion of the element, and the read is performed as an atomic operation.
Claim 23
Dependent Claim
92 words
A machine-readable medium comprising instructions which, when executed by a machine, cause the machine to perform the steps of: performing a first operation with respect to the linked-list data structure, the linked-list data structure including an element having a data portion and a pointer portion; and performing an unsynchronized traversal, comprising a mark and sweep garbage collection operation, of the linked-list data structure concurrently with the first operation; wherein the unsynchronized traversal includes performing a read of the pointer portion of the element, and the read is performed as an atomic operation.
Claim 24
Dependent Claim
19 words
The machine-readable medium of claim 18 wherein the first operation is a unsynchronized traversal of the linked-list data structure.
Claim 25
Dependent Claim
20 words
The machine-readable medium of claim 18 wherein the first operation is a further synchronized modification of the linked-list data structure.
Claim 26
Dependent Claim
120 words
A computer data signal embodied in a carrier wave and representing a sequence of instructions which, when executed by a machine, cause the machine to perform the steps of: modifying a linked-list data structure, the linked-list data structure including a first element having data and pointer portions, by the insertion or removal of a second element; updating the pointer portion of a first element to reflect the modification to the linked-list data structure, the step of updating comprising an atomic operation; and performing a first unsynchronized traversal of the linked-list data structure concurrently with the modification of the linked-list data structure, the first unsynchronized traversal comprising a mark and sweep garbage collection operation with respect to the linked-list data structure.
Claim 27
Dependent Claim
120 words
A computer data signal embodied in a carrier wave and representing a sequence of instructions which, when executed by a machine, cause the machine to perform the steps of: modifying a linked-list data structure, the linked-list data structure including a first element having data and pointer portions, by the insertion or removal of a second element; updating the pointer portion of a first element to reflect the modification to the linked-list data structure, the step of updating comprising an atomic operation; and performing a first unsynchronized traversal of the linked-list data structure concurrently with the modification of the linked-list data structure, the first unsynchronized traversal comprising a mark and sweep garbage collection operation with respect to the linked-list data structure.
Claim 28
Dependent Claim
102 words
A computer data signal embodied in a carrier wave and representing a sequence of instructions which, when executed by a machine, cause the machine to perform the steps of: performing a first operation with respect to a linked-list data structures, the linked-list data structure including an element comprising a data portion and a pointer portion; and performing an unsynchronized traversal, comprising a mark and sweep garbage collection operation of, the linked-list data structure concurrently with the first operation; wherein the unsynchronized traversal includes performing a read of the pointer portion of the element, and the read is performed as an atomic operation.
Claim 29
Dependent Claim
102 words
A computer data signal embodied in a carrier wave and representing a sequence of instructions which, when executed by a machine, cause the machine to perform the steps of: performing a first operation with respect to a linked-list data structures, the linked-list data structure including an element comprising a data portion and a pointer portion; and performing an unsynchronized traversal, comprising a mark and sweep garbage collection operation of, the linked-list data structure concurrently with the first operation; wherein the unsynchronized traversal includes performing a read of the pointer portion of the element, and the read is performed as an atomic operation.
References Cited (Backward Citations)
US4149243A
Cited
US5287521A
Cited
US5168554A
Cited
US5293600A
Cited
US5469567A
Cited
US5295262A
Cited
US5319778A
Cited
US5495609A
Cited
US5442758A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-07-12 | 2003-01-11 | 2003-07-13 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-07-12 | 2007-01-11 | 2007-07-13 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-07-12 | 2011-01-11 | 2011-07-13 | $7700.00 | Window Closed / Lapsed |