Method and apparatus for multi-process access to a linked-list

• US 8,977,651 B2
• Filed: 04/14/2004
• Issued: 03/10/2015
• Est. Priority Date: 04/14/2004
• Status: Active Grant

• Current Assignee: Valtrus Innovations Limited (f/k/a Dolya Holdco 9 Limited) (Key Patent Innovations Limited)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Lin, David Hsing
• Primary Examiner(s): Alam, Hosain
• Assistant Examiner(s): GMAHL, NAVNEET K
• Application Number:
  US10/823,845
• Publication Number:
  US 20050234933A1
• Time in Patent Office: 3,982 Days
• Field of Search: 707 1- 10, 707100-1041, 707200-205, 707500-505, 707/704, 707/800
• US Class Current: 707/800
• 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: G06F 9/526 Mutual exclusion algorithms

Abstract

Data is retrieved from a linked-list by locking the linked-list, retrieving data from an element in the linked-list, advancing to a subsequent element in the linked-list while a breakpoint is not encountered and marking the subsequent element as “in-use” when a breakpoint is encountered. A reference to the subsequent element is then created before the linked-list is unlocked.

Claims

1. A method for retrieving data comprising:

locking a linked list;

retrieving data from an element in said linked list and also

advancing to a subsequent element while a breakpoint is not encountered;

marking the subsequent element in said linked list as in-use when a breakpoint is encountered, wherein marking the subsequent element in said linked list as in-use comprises maintaining a count of a quantity of processes that require additional access to the element;

creating a recommencement reference to the subsequent element; and

unlocking said linked list.

2. The method of claim 1 further comprising:

locking said linked list;

determining a subsequent element in said linked list according to the recommencement reference; and

retrieving data from a determined subsequent element.

3. The method of claim 1 wherein creating a recommencement reference to the subsequent element comprises:

retrieving a pointer to the subsequent element;

determining a process identifier for a current process; and

associating the pointer with the process identifier.

4. A method for deleting an element from a linked list comprising:

determining if the element to be deleted is in-use;

updating a recommencement reference to the element to refer to a data element that is subsequent to the data element to be deleted when the element in is in-use, wherein said updating a recommencement reference to the element comprises;

discovering a pointer associated with a process identifier;

disassociating the process identifier from the pointer;

determining a pointer to a subsequent element; and

associating the process identifier with a newly determined pointer; and

deleting the element.

5. An apparatus for storing and retrieving data comprising:

processor to execute an instruction sequence;

memory for storing an instruction sequence;

input unit for receiving data;

first output unit for providing data according to a received data request;

one or more ancillary output units for providing data according to a received data request;

instruction sequences stored in the memory including;

data storage module that, when executed by the processor, minimally causes the processor to;

receive data from the input unit;

allocate a data element to accommodate the data;

create a reference to the data element;

store the reference in at least one of a header pointer and a forward pointer included in a preceding data element; and

store the data in the data element;

data service module that, when executed by the processor, minimally causes the processor to;

recognize a data request from the first output unit to the exclusion of all other data requests;

provide data to the first output unit from a data element according to a data element reference and also

advance the data element reference to a subsequent data element while a breakpoint is not encountered;

mark a subsequent data element as in-use when a breakpoint is encountered, wherein the data service module causes the processor to mark a subsequent data element as in-use by minimally causing the processor to increment a use counter included in a subsequent data element;

create a recommencement reference to a subsequent data element; and

enable recognition of other data requests.

6. The apparatus of claim 5 wherein the data service module, when executed by the processor, further minimally causes the processor to:

recognize a data request from the first output unit to the exclusion of all other data requests; and

provide data to the first output unit from a data element according to the recommencement reference.

7. The apparatus of claim 5 wherein the data service module causes the processor to create a recommencement reference by minimally causing the processor to:

retrieve a pointer to a data element subsequent to a current data element;

determine an identifier associated with the data request received from the first output unit; and

store a retrieved pointer and a determined identifier in an associative manner.

8. The apparatus of claim 5 wherein the data service module further minimally causes the processor to receive a delete data request from an output unit by minimally causing the processor to:

determine if a data element to be deleted is in-use;

update a recommencement reference to refer to a data element that is subsequent to the data element to be deleted; and

delete the data element according to a received delete data request.

9. The apparatus of claim 8 wherein the data service module causes the processor 10 update a recommencement reference by minimally causing the processor to:

discover a pointer according to a data request identifier; and

replace the pointer with a pointer to a data element that is subsequent to the data element to be deleted.

10. A non-transitory computer readable storage medium having imparted thereon one or more instruction sequences for storing and retrieving data comprising:

data storage module that, when executed by a processor, minimally causes the processor to;

receive data from an input unit;

allocate a data element to accommodate the data;

create a reference to the data element;

store the reference in at least one of a header pointer and a forward pointer included in a preceding data element; and

store the data in the data element;

data service module that, when executed by a processor, minimally causes the processor to;

recognize a data request from a first output unit to the exclusion of all other data requests;

provide data to a first output unit from a data element according to a data element reference and also

advance the data element reference to a subsequent data element while a breakpoint is not encountered;

mark a subsequent data element as in-use when a breakpoint is encountered, wherein the data service module causes a processor to mark a subsequent data element as in-use by minimally causing the processor to increment a use counter included in a subsequent data element;

create a recommencement reference to a subsequent data element; and

enable recognition of other data requests.

11. The non-transitory computer readable storage medium of claim 10 wherein the data service module, when executed by a processor, further minimally causes the processor to:

recognize a data request from a first output unit to the exclusion of all other data requests; and

provide data to a first output unit from a data element according to the recommencement reference.

12. The non-transitory computer readable storage medium of claim 10 wherein the data service module causes a processor to create a recommencement reference by minimally causing the processor to;

retrieve a pointer to a data element subsequent to a current data element;

determine an identifier associated with a data request received from a first output unit; and

store a retrieved pointer and a determined identifier in an associative manner.

13. The non-transitory computer readable storage medium of claim 10 wherein the data service module further minimally causes the processor to receive a delete data request from an output unit by minimally causing the processor to:

determine if a data element to be deleted is in-use;

update a recommencement reference to refer to a data element that is subsequent to the data element to be deleted; and

delete the data element according to a received delete data request.

14. The non-transitory computer readable storage medium of claim 13 wherein the data service module causes the processor to update a recommencement reference by minimally causing the processor to:

discover a pointer according to a data request identifier; and

replace the pointer with a pointer to a data element that is subsequent to the data element to be deleted.

15. An apparatus for storing and retrieving data comprising:

means for locking a linked list;

means for retrieving data from an element in said linked list and also

advancing to a subsequent element while a breakpoint is not encountered;

means for marking the subsequent element in said linked list as in-use when a breakpoint is encountered, wherein marking the subsequent element in said linked list as in-use comprises maintaining a count of a quantity of processes that require additional access to the element;

means for creating a recommencement reference to the subsequent element; and

means for unlocking said linked list.

16. The apparatus of claim 15 further comprising:

means for locking said linked list;

means for determining a subsequent element in said linked list according to the recommencement reference; and

means for retrieving data from the determined subsequent element.

17. The apparatus of claim 15 further comprising a means for deleting an element in said linked list.

18. The apparatus of claim 17 wherein the means for deleting an element comprises:

means for determining if the element to be deleted is in-use;

means for updating a reference to the element to refer to a subsequent element in said linked list when the element in is in-use; and

means for deleting the element.