Patent ID: 8271564

Claim:
A method of managing entries in a cuckoo hash table that is subject to manipulation by a plurality of concurrent processors, the method comprising: maintaining a plurality of keys, along with their respective data items, in the cuckoo hash table configured to support concurrent operation by the plurality of processors without using lockouts, each data item having an associated push flag; processing a first push command for the cuckoo hash table to move a data item from one location in the cuckoo hash table designated by a key to another location in the cuckoo hash table designated by the key, the first push command being associated with a first processor of the plurality of concurrent processors, the first command asserting the push flag of the data item being pushed; preventing concurrent processing of a second push command for the data item without using lockouts, wherein the second push command is associated with a second processor of the plurality of concurrent processors, by recognizing that the push flag is being asserted, wherein the first process to continues moving the data item while the push flag is being asserted, and wherein the second processor looks up the data item while the first processor is concurrently attempting to move that data item; wherein the processing includes associating the designated key with a push counter, wherein the push counter is changed in response to each push command involving the designated key; and wherein the preventing includes analyzing, by the second processor, the push counter of the designated key for a change by the first processor, which indicates an invalid condition associated with concurrent processing of a second push command for the entry.