Systems and methods of directory entry encodings
View Patent ↗In general, the invention relates to supporting multiple different character encodings in the same file system. In one embodiment, a method is provided for filename lookup that supports multiple character encodings. The method comprises storing filename data in a first character encoding into an indexed data structure. The method further comprises receiving filename data in a second encoding. The method also comprises looking up filename data in the indexed data structure using the second encoding.
1. A system for filename lookup that supports multiple character encodings, comprising:
a computer-readable data store that stores an indexed data structure comprising a plurality of data elements, wherein a data element is associated with a first key based on a standard character encoding, wherein the data element comprises an encoding tag identifying a first character encoding, the byte values of a name in the first character encoding, and address data for locating file data associated with the name; and
a computing device in communication with the data store and that is operative to:
receive a request to retrieve the data element, the request comprising the name in a second character encoding;
convert the name in the second character encoding into a second key, the second key based on the standard character encoding; and
retrieve at least the address data of the data element from the indexed data structure using the second key.
2. The system of claim 1 , wherein said name is a filename.
3. The system of claim 1 , wherein said name is a directory name.
4. The system of claim 1 , wherein the indexed data structure corresponds to a directory structure in a file system, wherein the plurality of data elements correspond to files and directories in the directory structure.
5. The system of claim 1 , wherein the byte values of the name comprise byte sequences that do not represent valid characters in the standard character encoding.
6. The system of claim 1 , wherein the indexed data structure comprises at least one of the following: b-tree, binary tree, tree, b+tree, sorted tree, Patricia tries, red-black trees, and flat-file directories.
7. The system of claim 1 , wherein said conversion comprises electronically converting the name in said first character encoding or said second character encoding into a converted name in said standard character encoding and applying a hash function to the converted name to produce said first key or said second key, said first key and said second key both comprising the same hash value.
8. The system of claim 7 , wherein said conversion further comprises regularizing the name before applying the hash function, the regularizing comprising one or more of the following: removing one or more problem characters, replacing one or more problem characters with one or more default characters, converting characters to a shared case, and normalizing.
9. The system of claim 1 , wherein the computing device is further operative to:
determine said first character encoding based on a first process and determine said second character encoding based on a second process.
10. A computer-implemented method for filename lookup that supports at least a first character encoding and a second character encoding, the method comprising:
receiving, at a computer system, a request to retrieve a data element from a data store that stores an indexed data structure, wherein the request to retrieve the data element comprises a name in the second character encoding, wherein the indexed data structure comprises a plurality of data elements, wherein the data element is associated in the indexed data structure with a first key based on a standard character encoding, wherein the data element as stored in the indexed data structure comprises an encoding tag identifying the first character encoding, the byte values of the name in the first character encoding, and address data for locating file data associated with the name;
converting, by the computer system, the name in the second character encoding into a second key, the second key based on the standard character encoding; and
retrieving, by the computer system, at least the address data of the data element from the indexed data structure using the second key.
11. The computer-implemented method of claim 10 , wherein the indexed data structure corresponds to a directory structure in a file system, wherein the plurality of data elements correspond to files and directories in the directory structure.
12. The computer-implemented method of claim 10 , wherein the byte values of the name comprise byte sequences that do not represent valid characters in the standard character encoding.
13. The computer-implemented method of claim 10 , wherein said conversion comprises electronically converting the name in said first character encoding or said second character encoding into a converted name in said standard character encoding and applying a hash function to the converted name to produce said first key or said second key, said first key and said second key both comprising the same hash value.
14. The computer-implemented method of claim 13 , wherein said conversion further comprises regularizing the name before applying the hash function, the regularizing comprising one or more of the following: removing one or more problem characters, replacing one or more problem characters with one or more default characters, converting characters to a shared case, and normalizing.
15. The computer-implemented method of claim 10 , further comprising:
determining said first character encoding based on a first process and determining said second character encoding based on a second process.
16. A computer-readable storage medium having instructions stored thereon for implementing, when the instructions are executed, filename lookup that supports at least a first character encoding and a second character encoding, the instructions comprising:
receiving a request to retrieve a data element from a data store that stores an indexed data structure, wherein the request to retrieve the data element comprises a name in the second character encoding, wherein the indexed data structure comprises a plurality of data elements, wherein the data element is associated in the indexed data structure with a first key based on a standard character encoding, wherein the data element as stored in the indexed data structure comprises an encoding tag identifying the first character encoding, the byte values of the name in the first character encoding, and address data for locating file data associated with the name;
converting the name in the second character encoding into a second key, the second key based on the standard character encoding; and
retrieving at least the address data of the data element from the indexed data structure using the second key.
17. The computer-readable storage medium of claim 16 , wherein said conversion comprises electronically converting the name in said first character encoding or said second character encoding into a converted name in said standard character encoding and applying a hash function to the converted name to produce said first key or said second key, said first key and said second key both comprising the same hash value.
18. The computer-readable storage medium of claim 16 , wherein the indexed data structure corresponds to a directory structure in a file system, wherein the plurality of data elements correspond to files and directories in the directory structure.