CN-122019479-A - New file creation acceleration method based on FAT file system

Abstract

The invention discloses a new file creation acceleration method based on a FAT file system, which is characterized in that in the mounting stage of the FAT file system, file names of all existing files are converted into hash values and unique index nodes are generated, a red-black tree containing a linked list is constructed for each directory, and then the red-black tree is combined into a nested directory tree according to directory father-son relations.

Inventors

• MA HUIXIAN
• LIU MINGLIANG

Assignees

• 珠海亿智电子科技有限公司

Dates

Publication Date

20260512

Application Date

20260120

Claims (4)

1. 1. A new file creation acceleration method based on FAT file system is characterized by comprising the following steps: In the FAT file system mounting stage, traversing layer by layer from a root directory, reading file names of all existing files in a storage medium, converting the file names into corresponding hash values, synchronously reading attribute information of all files, and generating unique index nodes for each file based on the attribute information; Creating a red-black tree for each directory, wherein all files under the same father directory are used as tree nodes of the red-black tree, each tree node comprises file names, hash values and index nodes of the files, each tree node is added into the red-black tree of the corresponding father directory by combining a red-black tree distribution rule and a linked list structure, and then the red-black trees corresponding to all directories completing the adding operation are combined into a nested directory tree according to father-son relations among the directories; When a new file is created, firstly acquiring the file name and attribute information of the file to be created, converting the file name of the file to be created into corresponding hash values, pre-generating brand-new index nodes based on the attribute information, positioning a target parent directory to be inserted into the file to be created from the nested directory tree according to a target creation path of the file to be created, searching whether tree nodes which are the same as the hash values of the file to be created exist in the target parent directory based on a red-black tree searching rule and a linked list comparison rule, and judging whether the file to be created is allowed to be created according to a searching result.
2. 2. The FAT file system-based new file creation acceleration method according to claim 1, wherein the adding each tree node to the red-black tree of the corresponding parent directory in combination with the red-black tree allocation rule and the linked list structure comprises: And in the process of adding new nodes to the red black tree of the same father directory, judging whether the red black tree of the father directory has inserted tree nodes with the same hash value as the tree nodes to be inserted or not based on the hash value of the tree nodes to be inserted, if not, judging that no hash conflict exists, adding the tree nodes to be inserted as new tree nodes to the red black tree of the father directory, if yes, judging that hash conflict exists, defining the inserted tree nodes with hash conflict as conflict tree nodes, storing the memory address of the tree nodes to be inserted in the conflict tree nodes, accessing the tree nodes to be inserted through the memory address, and forming a linked list with the conflict tree nodes as head nodes, and storing corresponding file names in the conflict tree nodes and the tree nodes to be inserted.
3. 3. The method for accelerating creation of new files based on FAT file system as claimed in claim 1, wherein said determining whether said files to be created are allowed to be created according to the search result includes determining that there is no file with a same name if there is no tree node with a same hash value, allowing said files to be created and inserting it as new nodes into red black tree of target parent directory, traversing linked list associated with current tree node if there is tree node with a same hash value, comparing whether file names stored by all tree nodes in linked list are the same as file names of said files to be created, if there is a same file name, not allowing said files to be created to create, discarding pre-generated index nodes, if there is a different file name, hash value and index node of said files to be created to be added to linked list tail.
4. 4. The method for accelerating creation of new files based on FAT file system according to claim 1, wherein the tree node corresponding to any directory file in the nested directory tree additionally stores an address pointing to a root node of a red-black tree of a lower subdirectory for traversing the red-black tree of the lower subdirectory.

Description

New file creation acceleration method based on FAT file system Technical Field The invention relates to the technical field of computer operating systems, in particular to a new file creation acceleration method based on a FAT file system. Background In a mainstream operating system (such as Linux operating system), the same name file must not exist in the same directory, and the FAT file system also follows the rule. To achieve this constraint, when a user creates a new file by specifying a file name through the file system, the file system first needs to search for whether there is a created file with the same name in the parent directory of the file to be created. For the typical implementation of the FAT file system (such as FATFS), the core mode of the duplicate name retrieval is that the file names of the files to be created are compared with the file names of all the created files in the father directory one by one in a character string. Note that the FAT file system stores file names by two structures, namely, a short file name directory entry and a long file name directory entry. When the storage space of the short file name directory entry can not hold all characters of the file name, the complete characters of the file name are required to be stored in a plurality of long file name directory entries and one short file name directory entry in a scattered way, at the moment, the long file name directory entry records the complete character information of the file name, and the short file name directory entry only stores part of characters of the file name (namely short file name variants). Correspondingly, for the created file under the father catalog, if the catalog item of the created file contains a long file name catalog item, the file name of the file to be created is preferentially compared with the complete file name stored in the long file name catalog item, and if only the short file name catalog item exists, the file name is directly compared with the file name stored in the short file name catalog item. Based on the above traversal comparison mechanism, the operation of searching whether all the created files and the files to be created are renamed or not under the same parent directory has the time complexity of O (n) (where n is the number of the created files under the parent directory), and the searching efficiency is very low. Disclosure of Invention Aiming at the problems, the invention provides a new file creation acceleration method based on a FAT file system, which mainly solves the problem that the searching efficiency of a FAT file system traversal comparison mechanism is low. In order to solve the technical problems, the technical scheme of the invention is as follows: A new file creation acceleration method based on FAT file system includes the following steps: In the FAT file system mounting stage, traversing layer by layer from a root directory, reading file names of all existing files in a storage medium, converting the file names into corresponding hash values, synchronously reading attribute information of all files, and generating unique index nodes for each file based on the attribute information; Creating a red-black tree for each directory, wherein all files under the same father directory are used as tree nodes of the red-black tree, each tree node comprises file names, hash values and index nodes of the files, each tree node is added into the red-black tree of the corresponding father directory by combining a red-black tree distribution rule and a linked list structure, and then the red-black trees corresponding to all directories completing the adding operation are combined into a nested directory tree according to father-son relations among the directories; When a new file is created, firstly acquiring the file name and attribute information of the file to be created, converting the file name of the file to be created into corresponding hash values, pre-generating brand-new index nodes based on the attribute information, positioning a target parent directory to be inserted into the file to be created from the nested directory tree according to a target creation path of the file to be created, searching whether tree nodes which are the same as the hash values of the file to be created exist in the target parent directory based on a red-black tree searching rule and a linked list comparison rule, and judging whether the file to be created is allowed to be created according to a searching result. In some embodiments, the adding each tree node to the red black tree of the corresponding parent directory in combination with the red black tree allocation rule and the linked list structure includes: And in the process of adding new nodes to the red black tree of the same father directory, judging whether the red black tree of the father directory has inserted tree nodes with the same hash value as the tree nodes to be inserted or not based on the hash value of the tree