Patent ID: 7805467

Claim:
A method, comprising: using a computer to perform transforming program instructions executable to implement a concurrent shared data structure from instructions that implement a concurrent data structure that relies on the existence of a garbage collection facility to manage storage reclamation to instructions that implement a concurrent data structure that does not rely on the existence of a garbage collection facility to manage storage reclamation; wherein said transforming comprises: providing program instructions executable to associate a reference count with each instance of the concurrent shared data structure; modifying the program instructions executable to implement the concurrent shared data structure such that they ensure cycle-free garbage; replacing program instructions executable to implement pointer accesses in the program instructions executable to implement the concurrent shared data structure with corresponding program instructions executable to implement counterpart pointer operations that are lock-free and that maintain the reference count associated with each instance of the concurrent shared data structure, wherein said replacing comprises replacing program instructions executable to implement an access that assigns a pointer value to a pointer variable with program instructions executable to implement one or more lock-free, reference-count-maintaining load, store, or copy operations; and providing program instructions executable to explicitly manage one or more local pointer variables using a destroy operation that is lock-free, that maintains a respective reference count contribution associated with local pointer variables on which it operates, and that is configured to implement: freeing storage associated with local pointer variables on which it operates in response to determining that a corresponding reference count contribution indicates zero, and otherwise decrementing the corresponding reference count contribution.