Systems and methods of directory entry encodings

• US 7,739,288 B2
• Filed: 09/17/2009
• Issued: 06/15/2010
• Est. Priority Date: 12/22/2006
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Isilon Systems Incorporated (Dell Technologies Inc.)
• Inventors: Lemar, Eric M., White, Nathan N.
• Primary Examiner(s): Trujillo; James
• Assistant Examiner(s): Spieler; William
• Application Number:
  US12/562,000
• Publication Number:
  US 20100011011A1
• Time in Patent Office: 271 Days
• Field of Search: 707/999.001, 707/999.003
• US Class Current: 707/741
• CPC Class Codes: G06F 16/166 File name conversion
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

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.

Claims

1. A method for filename lookup which supports multiple character encodings, the method comprising:

receiving, at a computer system, one or more requests to store one or more names into a data structure, each name represented by a byte value based on one of a plurality of character encodings;

converting, by the computer system, each of the names of the one or more requests into a key;

for each name of the one or more requests, storing, by the computer system, a data element indexed by the name'"'"'s key into the data structure, the data element comprising the name'"'"'s byte value, an identifier of the name'"'"'s character encoding, and address data for locating file data associated with the name;

receiving, at the computer system, a request to retrieve a data element associated with a requested name comprising a request byte value according to a request character encoding;

converting, by the computer system, the requested name into a request key; and

searching, by the computer system, the data structure for a data element related to the requested name using at least the request key.

2. The method of claim 1, wherein the searching comprises:

retrieving zero or more data elements indexed by the request key from the data structure; and

if one or more data elements are retrieved, comparing the requested name to each of the retrieved data elements until at least one match is found or all retrieved data elements have been compared.

3. The method of claim 2, wherein the comparing comprises, until at least one match is found or all retrieved data elements have been compared, for each of the retrieved data elements:

if the data element has a different character encoding than the request character encoding, converting the byte value of the data element into a converted byte value according to the request character encoding and comparing at least a portion of the converted byte value to at least a portion of the request byte value; and

if the data element has a same character encoding as the request character encoding, comparing at least a portion of the byte value of the data element to at least a portion of the request byte value.

4. The method of claim 2, wherein the searching further comprises, if zero data elements are retrieved and the requested name comprises untranslatable characters, performing a brute force search of the data structure.

5. The method of claim 4, wherein the brute force search comprises comparing the requested name to each of the data elements in the data structure until at least one match is found or all data elements in the data structure have been compared.

6. The method of claim 5, wherein the comparing the requested name to each of the data elements in the data structure comprises, until at least one match is found or all data elements in the data structure have been compared, for each data element in the data structure:

if the data element has a different character encoding than the request character encoding, converting the byte value of the data element into a converted byte value according to the request character encoding and comparing at least a portion of the converted byte value to at least a portion of the request byte value; and

if the data element has a same character encoding as the request character encoding, comparing at least a portion of the byte value of the data element to at least a portion of the request byte value.

7. The method of claim 2, wherein the at least one match is either an exact match or a best inexact match.

8. The method of claim 3, wherein the comparing at least a portion of the converted byte value or the byte value of the data element to at least a portion of the request byte value skips portions of the converted byte value, byte value of the data element, or request byte value, which represent characters within a list of characters to be skipped.

9. The method of claim 5, wherein the at least one match is either an exact match or a best inexact match.

10. The method of claim 1, wherein the address data comprises an identifier of metadata associated with the name.

11. A system for filename lookup which supports multiple character encodings, the system comprising:

a computer processor;

a memory;

a data structure stored on the memory; and

at least one executable software module executed by the computer processor and configured to;

receive one or more requests to store one or more names into the data structure, each name represented by a byte value based on one of a plurality of character encodings;

convert each of the names of the one or more requests into a key;

for each name of the one or more requests, store a data element indexed by the name'"'"'s key into the data structure, the data element comprising the name'"'"'s byte value, an identifier of the name'"'"'s character encoding, and address data for locating file data associated with the name;

receive a request to retrieve a data element associated with a requested name comprising a request byte value according to a request character encoding;

convert the requested name into a request key; and

search the data structure for a data element related to the requested name using at least the request key.

12. The system of claim 11, wherein the at least one executable software module is further configured to search by:

retrieving zero or more data elements indexed by the request key from the data structure; and

if one or more data elements are retrieved, comparing the requested name to each of the retrieved data elements until at least one match is found or all retrieved data elements have been compared.

13. The system of claim 12, wherein the at least one executable software module is configured to compare by, until at least one match is found or all retrieved data elements have been compared, for each of the retrieved data elements:

if the data element has a different character encoding than the request character encoding, converting the byte value of the data element into a converted byte value according to the request character encoding and comparing at least a portion of the converted byte value to at least a portion of the request byte value; and

if the data element has a same character encoding as the request character encoding, comparing at least a portion of the byte value of the data element to at least a portion of the request byte value.

14. The system of claim 12, wherein the at least one executable software module is further configured to search by, if zero data elements are retrieved and the requested name comprises untranslatable characters, performing a brute force search of the data structure.

15. The system of claim 14, wherein the at least one executable software module is configured to perform the brute force search by comparing the requested name to each of the data elements in the data structure until at least one match is found or all data elements in the data structure have been compared.

16. The system of claim 15, wherein the at least one executable software module is configured to compare by, until at least one match is found or all data elements in the data structure have been compared, for each data element in the data structure:

if the data element has a different character encoding than the request character encoding, converting the byte value of the data element into a converted byte value according to the request character encoding and comparing at least a portion of the converted byte value to at least a portion of the request byte value; and

if the data element has a same character encoding as the request character encoding, comparing at least a portion of the byte value of the data element to at least a portion of the request byte value.

17. The system of claim 12, wherein the at least one match is either an exact match or a best inexact match.

18. The system of claim 13, wherein the at least one executable software module is configured to compare at least a portion of the converted byte value or the byte value of the data element to at least a portion of the request byte value by skipping portions of the converted byte value, byte value of the data element, or request byte value, which represent characters within a list of characters to be skipped.

19. The system of claim 15, wherein the at least one match is either an exact match or a best inexact match.

20. The system of claim 11, wherein the address data comprises an identifier of metadata associated with the name.