Quick filename lookup using name hash

• US 10,614,032 B2
• Filed: 09/02/2015
• Issued: 04/07/2020
• Est. Priority Date: 12/17/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Pudipeddi, Ravisankar V, Ghotge, Vishal V, Thind, Ravinder S
• Primary Examiner(s): Wilson, Kimberly L
• Application Number:
  US14/842,963
• Publication Number:
  US 20150370821A1
• Time in Patent Office: 1,679 Days
• Field of Search: 707758
• CPC Class Codes: G06F 11/1417 Boot up procedures
• CPC Class Codes: G06F 16/137 Hash-based content-based indexing of textual data G06F16/31
• CPC Class Codes: G06F 16/152 using file content signatures, e.g. hash values
• CPC Class Codes: G06F 16/166 File name conversion
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 9/4403 Processor initialisation

Abstract

A method of updating a file record on at least one of a first one or more computer readable storage media including writing at least three contiguous DirectoryEntry data structures corresponding to a directory entry set, the directory entry set corresponding to a file, the writing occurring to the at least one of a first one or more computer readable storage media.

Claims

1. A method, comprising:

receiving a target file name for a new directory entry set to be stored on a computer-readable storage medium;

using a directory entry stored on the computer-readable storage medium to locate a conversion table, the directory entry being designated as a critical primary directory entry;

converting the target file name to a converted version of the target file name in accordance with the conversion table stored on the computer-readable storage medium;

generating a name hash of the converted version of the target file name, the name hash of the target file name being a function of the converted version of the target file name;

for each existing directory entry set of a plurality of existing directory entry sets stored on the computer-readable storage medium;

comparing the name hash with a corresponding name hash of a converted version of a file name of the existing directory entry set;

determining a sure verification of mismatch for the existing directory entry set when the name hash and the corresponding name hash do not match; and

allowing the target file name for the new directory entry set when a sure verification of mismatch has been determined for each of the plurality of existing directory entry sets,

wherein generating a name hash of the converted version of the target file name comprises;

determining the converted version of the target file name corresponds to one of a predetermined set of names, the predetermined set of names having a common prefix;

determining a second portion corresponding to at least a portion of the converted version of the target file name excluding the common prefix;

initializing a temporary value to a predetermined start value, the predetermined start value corresponding to the common prefix;

for each character of the second portion;

rotating the temporary value right by at least one bit; and

adding the second value to the temporary value; and

using the temporary value as the name hash.

2. The method recited in claim 1, the directory entry used to locate the conversion table comprising a field containing a value that indicates that the directory entry corresponds to the conversion table.

3. The method recited in claim 1, the target file name comprising a string of characters, and the converting of the target filename and the generating of the name hash of the converted target file name being performed integrally on the target filename on a character-by-character basis.

4. The method recited in claim 1, the converting of the target filename being performed prior to the generating of the name hash of the converted target filename.

5. The method recited in claim 1, each directory entry set storing the name hash of the converted version of the file name for that directory entry set.

6. The method recited in claim 1, further comprising:

determining that the name hash of the converted version of the target file name matches the name hash of the converted version of the file name of at least one of the existing directory entry sets; and

for each corresponding directory entry set having a matching name hash;

determining a sure verification of mismatch for the corresponding directory entry set when a comparison of the converted target file name to the converted version of the file name of the corresponding directory entry set indicates a mismatch.

7. The method as recited in claim 6, the comparison being only performed for directory entry sets with a matching name hash.

8. The method as recited in claim 1, further comprising:

when the name hash and the corresponding name hash of an existing directory entry set match, comparing a converted version of a full file name from that directory entry set to the converted target file name; and

rejecting the target file name for the new directory entry set when the converted target file name and the converted version of the full file name match.

9. The method as recited in claim 1, the plurality of existing directory entry sets stored on the computer-readable storage medium corresponding to all directory entry sets for a single directory on the computer-readable storage medium.

10. A first non-transitory computer-readable storage medium on which computer-executable instructions are stored which, when executed by a computing device, cause the computing device to perform operations comprising:

receiving a target file name for a new directory entry set to be stored on a second computer-readable storage medium;

using a directory entry stored on the second computer-readable storage medium to locate a conversion table, the directory entry being designated as a critical primary directory entry;

converting the target file name to a converted version of the target file name in accordance with the conversion table stored on the second computer-readable storage medium;

generating a name hash of the converted version of the target file name, the name hash of the target file name being a function of the converted version of the target file name;

for each existing directory entry set of a plurality of existing directory entry sets stored on the second computer-readable storage medium;

comparing the name hash with a corresponding name hash of a converted version of a file name of the existing directory entry set;

determining a sure verification of mismatch for the existing directory entry set when the name hash and the corresponding name hash do not match; and

allowing the target file name for the new directory entry set when a sure verification of mismatch has been determined for each of the plurality of existing directory entry sets

wherein generating a name hash of the converted version of the target file name comprises;

determining the converted version of the target file name corresponds to one of a predetermined set of names, the predetermined set of names having a common prefix;

determining a second portion corresponding to at least a portion of the converted version of the target file name excluding the common prefix;

initializing a temporary value to a predetermined start value, the predetermined start value corresponding to the common prefix;

for each character of the second portion;

rotating the temporary value right by at least one bit; and

adding the second value to the temporary value; and

using the temporary value as the name hash.

11. The first computer-readable storage medium recited in claim 10, the directory entry used to locate the conversion table comprising a field containing a value that indicates that the directory entry corresponds to the conversion table.

12. The first computer-readable storage medium recited in claim 10, the target file name comprising a string of characters, and the converting of the target filename and the generating of the name hash of the converted target file name being performed integrally on the target filename on a character-by-character basis.

13. The first computer-readable storage medium recited in claim 10, each directory entry set storing the name hash of the converted version of the file name for that directory entry set.

14. The first computer-readable storage medium recited in claim 10, the computer-executable instructions further causing the computing device to perform operations comprising:

determining that the name hash of the converted version of the target file name matches the name hash of the converted version of the file name of at least one of the existing directory entry sets; and

for each corresponding directory entry set having a matching name hash;

determining a sure verification of mismatch for the corresponding directory entry set when a comparison of the converted target file name to the converted version of the file name of the corresponding directory entry set indicates a mismatch.

15. The first computer-readable storage medium recited in claim 10, the computer-executable instructions further causing the computing device to perform operations comprising:

when the name hash and the corresponding name hash of an existing directory entry set match, comparing a converted version of a full file name from that directory entry set to the converted target file name; and

rejecting the target file name for the new directory entry set when the converted target file name and the converted version of the full file name match.

16. The first computer-readable storage medium as recited in claim 10, the plurality of existing directory entry sets stored on the second computer-readable storage medium corresponding to all directory entry sets for a single directory on the second computer-readable storage medium.

17. A computing device comprising a processor and a memory, the memory storing computer-executable instructions which, when executed by the processor, cause the computing device to perform operations comprising:

receiving a target file name for a new directory entry set to be stored on a computer-readable storage medium;

using a directory entry stored on the second computer-readable storage medium to locate a conversion table, the directory entry being designated as a critical primary directory entry;

converting the target file name to a converted version of the target file name in accordance with the conversion table stored on the computer-readable storage medium;

generating a name hash of the converted version of the target file name, the name hash of the target file name being a function of the converted version of the target file name;

for each existing directory entry set of a plurality of existing directory entry sets stored on the computer-readable storage medium;

comparing the name hash with a corresponding name hash of a converted version of a file name of the existing directory entry set;

determining a sure verification of mismatch for the existing directory entry set when the name hash and the corresponding name hash do not match; and

allowing the target file name for the new directory entry set when a sure verification of mismatch has been determined for each of the plurality of existing directory entry sets

wherein generating a name hash of the converted version of the target file name comprises;

determining the converted version of the target file name corresponds to one of a predetermined set of names, the predetermined set of names having a common prefix;

determining a second portion corresponding to at least a portion of the converted version of the target file name excluding the common prefix;

initializing a temporary value to a predetermined start value, the predetermined start value corresponding to the common prefix;

for each character of the second portion;

rotating the temporary value right by at least one bit; and

adding the second value to the temporary value; and

using the temporary value as the name hash.

18. The computing device recited in claim 17, the directory entry used to locate the conversion table comprising a field containing a value that indicates that the directory entry corresponds to the conversion table.

19. The computing device recited in claim 17, the target file name comprising a string of characters, and the converting of the target filename and the generating of the name hash of the converted target file name being performed integrally on the target filename on a character-by-character basis.

20. The computing device recited in claim 17, each directory entry set storing the name hash of the converted version of the file name for that directory entry set.

21. The computing device recited in claim 17, the computer-executable instructions further causing the computing device to perform operations comprising:

determining that the name hash of the converted version of the target file name matches the name hash of the converted version of the file name of at least one of the existing directory entry sets; and

for each corresponding directory entry set having a matching name hash;

determining a sure verification of mismatch for the corresponding directory entry set when a comparison of the converted target file name to the converted version of the file name of the corresponding directory entry set indicates a mismatch.

22. The computing device recited in claim 17, the computer-executable instructions further causing the computing device to perform operations comprising:

when the name hash and the corresponding name hash of an existing directory entry set match, comparing a converted version of a full file name from that directory entry set to the converted target file name; and

rejecting the target file name for the new directory entry set when the converted target file name and the converted version of the full file name match.

23. The computing device as recited in claim 17, the plurality of existing directory entry sets stored on the computer-readable storage medium corresponding to all directory entry sets for a single directory on the computer-readable storage medium.