Optimized iterators for RCU-protected skiplists

A system, comprising:

• a plurality of CPUs;
• a memory coupled to the CPUs, said memory including a computer readable storage medium tangibly embodying at least one program of instructions executable by the CPUs to perform optimized skiplist iterator operations for read-copy update (RCU)-protected skiplists, the operations comprising:
• entering an RCU read-side critical section;
• accessing an RCU-protected skiplist having more than one level of pointers between skiplist elements, including a lowest level in which all of the skiplist elements are linked in succession in search key order, and one or more higher levels in which some of the skiplist elements are skipped;
• performing a skiplist iterator operation that includes attempting to validate a cached pointer hint that references a skiplist element of the RCU-protected skiplist by determining whether an update operation has been performed on the RCU-protected skiplist since the pointer hint was cached by a previous invocation of the skiplist iterator operation, the pointer hint being validated if the update operation was not performed and being not validated if the update operation was performed, the skiplist element referenced by the pointer hint having an associated first key;
• if the pointer hint is validated, using the pointer hint to access the skiplist element, and dereferencing a pointer in the skiplist element to advance to a next skiplist element of the RCU-protected skiplist having an associated second key that is larger than the first key;
• if the pointer hint is not validated, performing a value-based skiplist iterator operation that includes traversing the RCU-protected skiplist using the first key to find the next skiplist element having the second key, the value-based skiplist iterator operation starting at a highest level of the skiplist, and moving down the skiplist levels toward the lowest skiplist level as necessary until the next skiplist element having the second key is reached;
• caching a new pointer hint that references the next skiplist element for use in a next invocation of the skiplist iterator operation;
• and
• exiting the RCU read-side critical section.

A computer program product, comprising:

• one or more computer readable data storage media;
• program instructions stored on the one or more computer readable data storage media for programming a data processing platform having a plurality of CPUs to perform optimized skiplist iterator operations for read-copy update (RCU)-protected skiplists, the operations comprising:
• entering an RCU read-side critical section;
• accessing an RCU-protected skiplist having more than one level of pointers between skiplist elements, including a lowest level in which all of the skiplist elements are linked in succession in search key order, and one or more higher levels in which some of the skiplist elements are skipped;
• performing a skiplist iterator operation that includes attempting to validate a cached pointer hint that references a skiplist element of an RCU-protected skiplist by determining whether an update operation has been performed on the RCU-protected skiplist since the pointer hint was cached by a previous invocation of the skiplist iterator operation, the pointer hint being validated if the update operation was not performed and being not validated if the update operation was performed, the skiplist element referenced by the pointer hint having an associated first key;
• if the pointer hint is validated, using the pointer hint to access the skiplist element, and dereferencing a pointer in the skiplist element to advance to a next skiplist element of the RCU-protected skiplist having an associated second key that is larger than the first key;
• if the pointer hint is not validated, performing a value-based skiplist iterator operation that includes traversing the RCU-protected skiplist using the first key to find the next skiplist element having the second key, the value-based skiplist iterator operation starting at a highest level of the skiplist, and moving down the skiplist levels toward the lowest skiplist level as necessary until the next skiplist element having the second key is reached;
• caching a new pointer hint that references the next skiplist element for use in a next invocation of the skiplist iterator operation;
• and
• exiting the RCU read-side critical section.