Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2007-12-11
2007-12-11
Lee, Andrew C. (Department: 2616)
Data processing: database and file management or data structures
Database design
Data structure types
C710S007000
Reexamination Certificate
active
10805095
ABSTRACT:
One embodiment of the present invention provides a system that supports concurrent accesses to a skip list that is lock-free, which means that the skip list can be simultaneously accessed by multiple processes without requiring the processes to perform locking operations. During a node deletion operation, the system receives reference to a target node to be deleted from the skip list. The system marks a next pointer in the target node to indicate that the target node is deleted, wherein next pointer contains the address of an immediately following node in the skip list. This marking operation does not destroy the address of the immediately following node, and furthermore, the marking operation is performed atomically and thereby without interference from other processes. The system then atomically modifies the next pointer of an immediately preceding node in the skip list to point to an immediately following node in the skip list, instead of pointing to the target node, thereby splicing the target node out of the skip list.
REFERENCES:
patent: 6493706 (2002-12-01), Mead et al.
patent: 6505283 (2003-01-01), Stoney
patent: 6687699 (2004-02-01), Courey, Jr.
patent: 6816945 (2004-11-01), Harris et al.
patent: 6988180 (2006-01-01), Kadatch
patent: 7065765 (2006-06-01), Cadden et al.
patent: 7117502 (2006-10-01), Harris
patent: 2001/0056420 (2001-12-01), Steele et al.
patent: 2003/0120623 (2003-06-01), Cadden et al.
Publication entitled “The Repeat Offender Problem: A Lock-Free Mechanism for Supporting Dynamic-Sized Data Structures”, by Maurice Herlihy et al.
Publication entitled “A Skip List Cookbook”, by William Pugh, UMIACS-TR-89-72.1, CS-TR-2286.1, Jul. 1989, Revised Jun. 1990.
Publication entitled “Concurrent Maintenance of Skip Lists” by William Pugh et al., CS-TR-2222.1, Apr. 1989, Revised Jun. 1990.
Lee Andrew C.
Park Vaughan & Fleming LLP
SUN Microsystems, Inc
LandOfFree
Method and apparatus for implementing a lock-free skip list... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for implementing a lock-free skip list..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for implementing a lock-free skip list... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3827154