I discovered recently that the hazard pointer technique has a patent application if not an actual patent assigned to it. Can I get clarification on this?
Also, would like some indication on whether the following idea would even remotely violate any possible patent on the hazard pointer technique:
Some structure containing pointers to objects which can be iterated. Take some tree or map as an example.
Some set of threads which iterate the tree using a reader writer lock.
The readers need to keep the read lock held for a long time thus writers get starved in this system.
Solution: Readers and writers obtain a handle to resource before starting to access the resource and drop the handle after accessing the resource. The handle is obtained from an array of counters. These counters serve as the "hazard pointer". Each active array entry is an indication of a thread with interest in a set of objects potentially marked for deletion. This is described below:
When a writer updates an entry it doesn't update in place. Instead, the original entry is marked as deleted and stamped with the the current handle counter value of the handle system and placed on a delete queue. The writer then stores a new value into the structure and the handle counter is incremented.
When readers obtain a handle, the current handle counter is stored in a slot in the handle array assigned to the reader.
So how is the data the reader has a pointer to protected? Via the counter handle. The processor of the deletion queue ensures that no value in the handle counter array is less or equal to the counter value stamped on the item to be deleted before actually deleting it.
The handle counter is a 64 bit integer which won't overflow easily. I have a procedure for re-setting the counter in the event of imminent overflow but I won't describe it here in the interest of space. ( Ala Fermat's last theorem. )