Read-only access without blocking via access vectors

A computer implemented method for maintaining a linked data structure stored in a computer system capable of processing the stored data as addressable object nodes, such that any node may be modified prior to the completion of outstanding read only accesses to that node, comprising the steps of:

• maintaining an access vector for each of the nodes, each access vector including an access counter for maintaining an access count value corresponding to how many processes have read access to a first node, a link for maintaining a pointer to a next node and a deallocation flag for indicating to readers whether to delete the first node;
• maintaining further access vectors for the nodes, each of the further access vectors including an adjustment counter for maintaining a value corresponding to how many processes have read access to a second node and a nil link for stopping propagation of adjustments to the data structure, wherein said adjustment counter eliminates the necessity of adjustments to an access count of an access vector associated with said adjustment counter;
• adding one or more links to the data structure, wherein when a link associated with an access vector is added to point to a third node, the value of the access count of the third node and the values of the access counts of all nodes indirectly pointed to by the added link are incremented by the value of the access count of the access vector associated with the added link;
• deleting links from the data structure, wherein when a link associated with an access vector is deleted from a fourth node, the value of the access count of the fourth node and the value of the access counts of all nodes previously indirectly pointed to by the deleted link are decreased by the value of the access count of the access vector associated with the deleted link;
• and
• deleting a fifth node by:
• (1) deleting all links pointing to said fifth node to thereby make said fifth node unreachable by readers;
• (2) atomically saving a current value of an adjustment counter for said fifth node in a temporary adjustment counter, and setting said adjustment counter of said fifth node to zero;
• (3) for all out-pointer links in said fifth node:
• atomically setting the deallocation flag for said fifth node, and setting the value of the access counter of said fifth node equal to a temporary access counter;
• and
• reducing said temporary adjustment counter by said temporary access counter;
• (4) atomically changing said temporary adjustment counter by adding to it said adjustment counter, and storing said temporary adjustment counter result back into said adjustment counter;
• and
• (5) if the result in step 4 was zero, deleting said out-pointer links of said fifth node and deallocating said fifth node.

A computer implemented method for maintaining linked data structures stored in a computer system capable of processing the stored data as addressable object nodes, such that any node may be at least one of modified and traversed prior to the completion of outstanding read only accesses to said any node, comprising the steps of:

• maintaining an access vector for each node;
• designating an access pointer for each access vector, said access pointer pointing to the location of a next node;
• designating an access counter for each access vector, said access counter maintaining the number of read only accesses to said next node;
• and
• traversing from a first node to a second node by:
• (1) incrementing the access counter of said first node, and
• (2) fetching the access pointer of said second node, wherein said second node is the next node with respect to said first node.

A system for maintaining linked data structures stored in a computer capable of processing the stored data as addressable object nodes, such that any data object node may be at least one of modified and traversed prior to the completion of outstanding read only accesses to said any data object node, comprising:

• first means for maintaining an access vector for each data object node, said access vector including an access pointer which points to the location of a next node, and an access counter which maintains the number of read only accesses to said next node;
• and
• second means for performing read only accesses from a first node to a second node, comprising:
• (a) means for incrementing the access counter of the first node;
• and
• (b) means for fetching the access pointer of the second node, and thereby determining the address of the second node, wherein the second node is the next node with respect to the first node.