Method and apparatus for managing a linked-list data structure

• US 5,924,098 A
• Filed: 06/30/1997
• Issued: 07/13/1999
• Est. Priority Date: 06/30/1997
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Kluge, Kevin L
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Coby, Frantz
• Application Number:
  US08/887,339
• Time in Patent Office: 743 Days
• Field of Search: 707/8, 707/100, 707/206, 707/101, 707/102
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database

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.

Claims

1. 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.

2. The computer-implemented method of claim 1 including performing concurrently a plurality of unsynchronized traversals of the linked-list data structure.

3. 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.

4. 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.

5. 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.

6. The computer-implemented method of claim 1 wherein the modification of the linked-list data structure is a synchronous operation.

7. 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.

8. 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.

9. 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.

10. 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.

11. 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.

12. 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.

13. 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.

14. The machine-readable medium of claim 9 wherein the step of modifying the linked-list data structure is a synchronous operation.

15. 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.

16. The computer-implemented method of claim 15 wherein the first operation is a further unsynchronized traversal of the linked-list data structure.

17. The computer-implemented method of claim 15 wherein the first operation is a further synchronized modification of the linked-list data structure.

18. 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.

19. The machine-readable medium of claim 18 wherein the first operation is a unsynchronized traversal of the linked-list data structure.

20. The machine-readable medium of claim 18 wherein the first operation is a further synchronized modification of the linked-list data structure.

21. 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.

22. 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.