Patent ID: 9274716
Filing Date: 2016-03-01
CPC Classification: G06F

Claim Text:
1. A method for freeing nodes, comprising: maintaining, in a network storage system, a hierarchical data structure representing data stored in the network storage system, the hierarchical data structure including multiple nodes, where a first node from among the multiple nodes includes: a link count to indicate a number of direct references to the first node; a sibling count to indicate a number of nodes that have the first node as a pre-image, and a delete count associated with a child pointer that points to a child node of the first node, where the delete count is incremented to track removed references to the child node to avoid having to update a reference count of the child node if the first node is modified; analyzing a direct reference status of the first node based on the link count to determine that there are no direct references to the first node; analyzing the sibling count of the first node without analyzing a sibling count of any other node, to determine if the first node can be freed, the sibling count indicating a number of nodes that have the first node as a pre-image; computing a difference between the delete count and the sibling count; determining that the link count and the difference between the delete count and the sibling count indicate that no other node points to the child node; and freeing the first node after resolving pointers in a copy of the first node to point directly to a different child node.