Method and apparatus for lock-free, non-blocking hash table

Details Method and apparatus for lock-free, non-blocking hash table Method and apparatus for lock-free, non-blocking hash table

2006-01-17

2006-01-17

Peikari, B. James (Department: 2189)

Electrical computers and digital processing systems: memory

Address formation

Hashing

C711S221000, C707S793000, C707S793000, C707S793000

Reexamination Certificate

active

06988180

ABSTRACT:
A method and apparatus are provided for an efficient lock-free, non-blocking hash table. Under one aspect, a linked list of nodes is formed in the hash table where each node includes a protected pointer to the next node in the list and a reference counter indicating the number of references currently made to the node. The reference counter of a node must be zero and none of the protected pointers in a linked list can be pointing at the node before the node can be destroyed. In another aspect of the invention, searching for a node in the hash table with a particular key involves examining the hash signatures of nodes along a linked list and only comparing the key of a node to a search key of the node if the hash signature of the node matches a search hash signature.

REFERENCES:
patent: 5047918 (1991-09-01), Schwartz et al.
patent: 5412384 (1995-05-01), Chang et al.
patent: 6360220 (2002-03-01), Forin
patent: 6457173 (2002-09-01), Gupta et al.
patent: 2002/0174405 (2002-11-01), Janssen
patent: 2004/0054807 (2004-03-01), Harvey et al.
Maged M. Michael, “Safe Memory Reclamation for Dynamic Lock-Free Objects Using Atomic Reads and Writes,” Inthe 21stAnnual ACM Symposium on Principles of Distributed Computing,pp. 21-30, Jul. 2002.
Maged M Michael, “High Performance Dynamic Lock-Free Hash Tables and List-Based Sets,” Inthe 14thAnnual ACM Symposium on Parallel Algorithms and Architectures,pp. 73-82, Aug. 2002.
Maged M. Michael and Michael L. Scott, “Correction of a Memory Management Method for Lock-Free Data Structures,” Technical Report TR599, Computer Science Department, University of Rochester, Dec. 1995.
Maged M. Michael and Michael L. Scott, “Simple Fast, and Practical non-Blocking and Blocking Concurrent Quene Algorithms,”In Proceedings of the 15thAnnual ACM Symposium on Principles of Distributed Computing,pp. 267-275, May 1996.
John D. Valois, “Implementing Lock-Free Queues,” In the7thInternational Conference on Parallel and Distributed Computing Systems,Las Vegas, NV, Oct. 1994.
John D. Valois, “Lock-Free Linked Lists Using Compare-and-Swap,” InProceedings of the 14thAnnual ACM Symposium on Principles of Distributed Computing, International Conference on Parallel and Distributed Computing,pp. 214-222, Aug. 1995.

Affiliated with

Also associated with

Rating

Method and apparatus for lock-free, non-blocking hash table 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 lock-free, non-blocking hash table, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for lock-free, non-blocking hash table will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3552022