# US 2012/0254139 A1 · Providing lock-based access to nodes in a concurrent linked list

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2012/0254139 A1
- Document ID: US20120254139A1
- Status: Published application
- Kind: A1
- Application number: 13/524,665
- Filed: 2012-06-15
- Published: 2012-10-04
- Earliest claimed: 2009-04-22
- Assignees: Microsoft Corporation
- Inventors: Chunyan Song; Joshua Phillips; John Duffy; Tim Harris; Stephen H. Toub; Boby George
- Web page: https://patentgrep.com/patent/US20120254139A1

## CPC

- G06F 16/2343: {Locking methods, e.g. distributed locking or locking implementation details}
- G06F 9/526: {Mutual exclusion algorithms}
- G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method of providing lock-based access to nodes in a concurrent linked list includes providing a plurality of striped lock objects. Each striped lock object is configured to lock at least one of the nodes in the concurrent linked list. An index is computed based on a value stored in a first node to be accessed in the concurrent linked list. A first one of the striped lock objects is identified based on the computed index. The first striped lock object is acquired, thereby locking and providing protected access to the first node.

## Claims

### Claim 1

A method of providing lock-based access to nodes in a concurrent linked list, comprising:
providing a plurality of striped lock objects, each striped lock object configured to lock at least one of the nodes in the concurrent linked list;
computing an index based on a value stored in a first node to be accessed in the concurrent linked list;
identifying a first one of the striped lock objects based on the computed index; and
acquiring the first striped lock object, thereby locking and providing protected access to the first node.

### Claim 2 (depends on 1)

The method of claim 1, wherein the acquiring of the first striped lock object locks a plurality of non-contiguous ones of the nodes in the concurrent linked list including the first node.

### Claim 3 (depends on 1)

The method of claim 1, and further comprising:
identifying a hash code based on the value stored in the first node; and
computing the index based on the identified hash code and a total number of the striped lock objects.

### Claim 4 (depends on 3)

The method of claim 3, and further comprising:
performing a logical AND operation on the hash code and a constant value; and
computing the index by dividing a result of the AND operation by the total number of the striped lock objects.

### Claim 5 (depends on 1)

The method of claim 1, and further comprising:
computing a plurality of indices based on values stored in a first plurality of nodes to be accessed in the concurrent linked list; and
sorting the plurality of indices, thereby generating sorted indices.

### Claim 6 (depends on 5)

The method of claim 5, and further comprising:
identifying a first set of the plurality of striped lock objects based on the plurality of indices; and
acquiring the striped lock objects in the first set in an order that is based on the sorted indices, thereby locking and providing protected access to at least the first plurality of nodes.

### Claim 7 (depends on 1)

The method of claim 1, and further comprising:
determining whether the locked first node has changed prior to being locked; and
releasing the first striped lock object and attempting to reacquire a striped lock object on the first node when it is determined that the first node has changed prior to being locked.

### Claim 8 (depends on 7)

The method of claim 7, and further comprising:
performing an operation on the locked first node when it is determined that the first node has not changed prior to being locked; and
releasing the lock on the first node upon completion of the operation.

### Claim 9 (depends on 1)

The method of claim 1, and further comprising:
performing a find operation that attempts to find a node in the concurrent linked list that contains a user-specified value.

### Claim 10 (depends on 9)

The method of claim 9, and further comprising
traversing nodes of the concurrent linked list while one of the plurality of striped lock objects is being held until a node containing the user-specified value is found or until an end of the list has been reached.

### Claim 11 (depends on 10)

The method of claim 10, and further comprising:
when a node containing the user-specified value is found, returning the node containing the user-specified value.

### Claim 12 (depends on 11)

The method of claim 11, and further comprising:
determining whether any of the nodes were moved during the traversing;
when a node containing the user-specified value is not found and it is determined that none of the nodes was moved during the traversing, returning an indication that the user-specified value is not in the linked list.

### Claim 13 (depends on 11)

The method of claim 11, and further comprising:
determining whether any of the nodes were moved during the traversing;
when a node containing the user-specified value is not found and it is determined that at least one of the nodes was moved during the traversing, repeating the traversing of the nodes of the concurrent linked list while one of the plurality of striped lock objects is being held to again attempt to find a node containing the user-specified value.

### Claim 14 (depends on 13)

The method of claim 13, and further comprising:
when a node containing the user-specified value is not found and it is determined that at least one of the nodes was moved during the traversing, acquiring all of the striped lock objects to freeze the concurrent linked list; and
repeating the traversing of the nodes of the concurrent linked list while it is frozen to again attempt to find a node containing the user-specified value.

### Claim 15 (depends on 10)

The method of claim 10, and further comprising:
determining whether any of the nodes were moved during the traversing by assigning version numbers to the nodes, and modifying the version numbers based on movement of the nodes.

### Claim 16 (depends on 15)

The method of claim 15, wherein determining whether any of the nodes were moved during the traversing further comprises:
tracking the version numbers of two adjacent nodes at a time in a hand-over-hand manner.

### Claim 17

A computer-readable storage medium storing computer-executable instructions for performing a method of providing lock-based access to nodes in a concurrent linked list using a plurality of striped lock objects, each striped lock object having a corresponding index and configured to lock at least one of the nodes in the concurrent linked list, the method comprising:
computing an index based on a value stored in a first node to be accessed in the concurrent linked list;
identifying a first one of the striped lock objects based on the computed index; and
acquiring the first striped lock object, thereby locking and providing protected access to the first node.

### Claim 18 (depends on 17)

The computer-readable storage medium of claim 17, wherein the acquiring of the first striped lock object locks a plurality of non-contiguous ones of the nodes in the concurrent linked list including the first node.

### Claim 19 (depends on 17)

The computer-readable storage medium of claim 17, wherein the method further comprises:
identifying a hash code based on the value stored in the first node; and
computing the index based on the identified hash code and a total number of the striped lock objects.

### Claim 20

A method of providing lock-based access to nodes in a concurrent linked list, comprising:
providing a plurality of striped lock objects, each striped lock object having a corresponding index and configured to lock at least one of the nodes in the concurrent linked list, and wherein at least one of the striped lock objects is configured to lock a plurality of the nodes;
computing an index based on a hash code corresponding to a value store in a first node to be accessed in the concurrent linked list, and based on a total number of the striped lock objects;
identifying a first one of the striped lock objects based on the computed index; and
acquiring the first striped lock object, thereby locking and providing protected access to at least the first node.
