System and method for removing deleted entries in file systems based on write-once or erase-slowly media
First Claim
1. In a computer system comprising a processor and write once or erase slowly memory, said memory storing a file system including a file system directory in the structure of a linked list of nodes, each node identifying a corresponding file in the file system, each node comprising file identification information, a next pointer field which contains a pointer to a next node in the linked list, a replacement pointer field, which when set to contain a replacement pointer, points to a replacement node which replaces the node, and a delete flag field, which indicates whether the node has been deleted, a method for removing deleted and replaced nodes from the linked list directory, comprising the steps of:
- (a) determining in the linked list a sequence of nodes that contain either a replacement pointer in the replacement pointer field to indicate that the corresponding file is replaced or a delete flag set to indicate that the corresponding file is deleted;
(b) if the number of nodes in the sequence is greater than a first threshold, creating a new node that contains file identification information of a node which immediately precedes the sequence, the next pointer field of the new node containing a pointer to a next node after the sequence of nodes; and
(c) modifying the replacement pointer field of the node which immediately precedes the sequence to point to the new node;
wherein the number of nodes in the linked list is decreased.
0 Assignments
0 Petitions
Accused Products
Abstract
A system and method for deleting entries of a file system directory located on write-once or erase-slowly media utilizes a technique to collapse linked lists of nodes containing file system information to remove nodes of files that have been deleted or replaced. By collapsing the linked lists, access time to the file system does not increase by eliminating the need of traversing long lists of deleted or replaced nodes.
-
Citations
7 Claims
-
1. In a computer system comprising a processor and write once or erase slowly memory, said memory storing a file system including a file system directory in the structure of a linked list of nodes, each node identifying a corresponding file in the file system, each node comprising file identification information, a next pointer field which contains a pointer to a next node in the linked list, a replacement pointer field, which when set to contain a replacement pointer, points to a replacement node which replaces the node, and a delete flag field, which indicates whether the node has been deleted, a method for removing deleted and replaced nodes from the linked list directory, comprising the steps of:
-
(a) determining in the linked list a sequence of nodes that contain either a replacement pointer in the replacement pointer field to indicate that the corresponding file is replaced or a delete flag set to indicate that the corresponding file is deleted; (b) if the number of nodes in the sequence is greater than a first threshold, creating a new node that contains file identification information of a node which immediately precedes the sequence, the next pointer field of the new node containing a pointer to a next node after the sequence of nodes; and (c) modifying the replacement pointer field of the node which immediately precedes the sequence to point to the new node; wherein the number of nodes in the linked list is decreased. - View Dependent Claims (2, 3)
-
-
4. In a computer system comprising a processor and write once or erase slowly memory, said memory storing a file system including a file system directory in the structure of a linked list of nodes, each node identifying a corresponding file in the file system, each node comprising file identification information, a next pointer field which contains a pointer to a next node in the linked list, a replacement pointer field, which when set to contain a replacement pointer, points to a replacement node which replaces the node, and a delete flag field, which indicates whether the node has been deleted, a method for removing deleted and replaced nodes from the linked list directory, comprising the steps of:
-
(a) determining in the linked list a sequence of nodes that contain either a replacement pointer in the replacement pointer field to indicate that the corresponding file is replaced or a delete flag set to indicate that the corresponding file is deleted; (b) identifying a set of "n" of replaceable nodes in the sequence; (c) identifying a sub-sequence of the sequence of deleted and replaced nodes to be the nodes between a current node of the set of n replaceable nodes and the end of the sequence; (d) if the number of nodes in the sub-sequence is greater than a first threshold, (1) creating a new node that contains file identification information of the current node, the next pointer field of the new node containing a pointer to a next node after the sequence of nodes, and (2) modifying the next pointer of the current node to point to the new node; (e) performing steps (c) and (d) for each node of the set of nodes until a new node is created; (f) if a new node is not created, creating a new node that contains file identification information of a node which immediately precedes the sequence, the next pointer field of the new node containing a pointer to a next node after the sequence of nodes, and modifying the replacement pointer field of the node which immediately precedes the sequence to point to the new node; wherein the number of nodes in the linked list is decreased.
-
-
5. A computer system comprising:
-
a processor; write once or erase slowly memory coupled to the processor; a file system comprising files stored in the memory; a file system directory contained within the file system, the file system directory comprising a structure of a linked list of nodes, each node identifying a corresponding file in the file system, each node comprising file identification information, a next pointer field which contains a pointer to a next node in the linked list, a replacement pointer field, which when set to contain a replacement pointer, points to a replacement node which replaces the node, and a delete flag field, which indicates whether the node has been deleted; a memory controller coupled to control the memory, said controller;
determining in the linked list a sequence of nodes that contain either a replacement pointer in the replacement pointer field to indicate that the corresponding file is replaced or a delete flag set to indicate that the corresponding file is deleted;
if the number of nodes in the sequence is greater than a first threshold, said controller creating a new node that contains file identification information of a node which immediately precedes the sequence, the next pointer field of the new node containing a pointer to a next node after the sequence of nodes, and modifying the replacement pointer field of the node which immediately precedes the sequence to point to the new node;wherein the number of nodes in the linked list is decreased. - View Dependent Claims (6)
-
-
7. A computer system comprising:
-
a processor; write once or erase slowly memory coupled to the processor; a file system comprising files stored in the memory; a file system directory contained within the file system, the file system directory comprising a structure of a linked list of nodes, each node identifying a corresponding file in the file system, each node comprising file identification information, a next pointer field which contains a pointer to a next node in the linked list, a replacement pointer field, which when set to contain a replacement pointer, points to a replacement node which replaces the node, and a delete flag field, which indicates whether the node has been deleted; means for determining in the linked list a sequence of nodes that contain either a replacement pointer in the replacement pointer field to indicate that the corresponding file is replaced or a delete flag set to indicate that the corresponding file is deleted; and if the number of nodes in the sequence is greater than a first threshold, means for creating a new node that contains file identification information of a node which immediately precedes the sequence, the next pointer field of the new node containing a pointer to a next node after the sequence of nodes, and modifying the replacement pointer field of the node which immediately precedes the sequence to point to the new node; wherein the number of nodes in the linked list is decreased.
-
Specification