Patent · US Active

Optimized iterators for RCU-protected skiplists

US10311039B2 · kind B2 · utility

0Cited by

4References

20Claims

0Family size

Assignee

International Business Machines Corporation · US

Inventors

Paul E. McKenney · Beaverton, US
Manuel Mayr · Walldorf, DE

Key dates

Filing date	Dec 7, 2016
Grant date	Jun 4, 2019
Priority date	—
Expiry date	Jul 5, 2037

Classification

Technology area (CPC G)Physics
CPC primaryG06F16/2365
WIPO fieldComputer technology
WIPO sectorElectrical engineering

Abstract

An optimized skiplist iterator technique for RCU-protected skiplists. A skiplist iterator operation may attempt to validate a cached pointer hint that references a skiplist element of an RCU-protected skiplist, the skiplist element having an associated first key. If the pointer hint is validated, the pointer hint may be dereferenced to access the skiplist element. A pointer in the skiplist element may be dereferenced to advance to a next skiplist element of the RCU-protected skiplist, the next skiplist element having an associated second key that is larger than the first key. If the pointer hint is not validated, a value-based skiplist iterator operation may be performed that includes traversing the RCU-protected skiplist using the first key to find the next skiplist element having the second key. A new pointer hint that references the next skiplist element may be cached for use in a next invocation of the skiplist iterator operation.

Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.