System and method for accessing external memory using hash functions in a resource limited device

• US 6,535,867 B1
• Filed: 11/01/1999
• Issued: 03/18/2003
• Est. Priority Date: 09/29/1999
• Status: Expired due to Term

• Current Assignee: Celsius Research Limited, Qualcomm, Inc.
• Original Assignee: JatoTech Affiliates LP (JatoTech Ventures Inc), JatoTech Ventures LP (JatoTech Ventures Inc), Mayfield Associates Fund VI, Mayfield Ix, Mayfield Principals Fund II, Mayfield Xi, Mayfield XI Qualified, The Chip Trust III, Unger-Luchsinger Family Trust
• Inventors: Waters, Christopher J. F.
• Primary Examiner(s): Robinson, Greta
• Assistant Examiner(s): Le, Debbie M.
• Application Number:
  US09/431,016
• Time in Patent Office: 1,233 Days
• Field of Search: 707/10, 707/1, 707/2, 707/101, 709/226, 709/228, 711/216
• US Class Current: 1/1
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: G06F 16/9014 hash tables
• 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/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A system and method that computes a hash function based upon the file name, e.g. a URI, that is to be identified in a look-up table stored in external memory. The hash value is multiplied by a first multiplier. The result is used as a pointer to a lookup table that is stored in external memory. The present invention avoids the need to perform string comparisons or to store any file names or addresses on the server.

Claims

1. A computer based method for accessing data files in an external memory without requiring a data file path name to be stored on internal memory, comprising the steps of:

receiving a data file path name;

determining a hash value of said data file path name;

indexing an index block in an external memory using an index address corresponding to said hash value;

identifying an offset value stored at said index address; and

retrieving a file corresponding to said data file path name by accessing an offset address corresponding to said offset value.

2. The method of claim 1 further comprising the step of verifying the retrieved file by a collision resolution technique.

3. The method of claim 1 further comprising determining a second hash value based on said data file path name and comparing said second hash value to a value stored within said file corresponding to said data file path name.

4. The method of claim 1 wherein the external memory comprises an EEPROM.

5. The method of claim 1 wherein the internal memory comprises a static random access memory.

6. The method of claim 1 wherein determining the hash value of said data file path name produces a value within a predetermined range of hash values.

7. The method of claim 6 wherein the predetermined range of hash values corresponds directly to a single block of consecutive memory address locations in the external memory.

8. The method of claim 6 wherein the predetermined range of hash values corresponds to one or more blocks of memory address locations in the external memory.

9. The method of claim 1 wherein determining the hash value of said data file path name comprises calculating an unsigned 8-bit sum of the ASCII values of the characters in said data file path name.

10. The method of claim 1 wherein determining the hash value of said data file path name comprises calculating an unsigned 8-bit sum of the ASCII values of the characters in said data file path name and multiplying this sum by a multiplicative factor.

11. The method of claim 1 wherein the computer is a resource limited computer.

12. A computer based apparatus for accessing data files in an external memory without requiring a data file path name to be stored in internal memory, comprising:

receiving means for receiving a data file path name;

hashing means for determining a hash value of said data file path name;

indexing means for indexing an index block in an external memory using an index address corresponding to said hash value;

identifying means for identifying an offset value stored at said index address; and

retrieving means for retrieving a file corresponding to said data file path name by accessing an offset address corresponding to said offset value.

13. The computer based apparatus of claim 12, further comprising verifying means for verifying the identity of the retrieved file.

14. The computer based apparatus of claim 12 wherein determining a hash value of said data file path name comprises calculating an unsigned 8-bit sum of the ASCII values of the characters in said data file path name.

15. The computer based apparatus of claim 12 wherein determining a hash value of said data file path name comprises calculating an unsigned 8-bit sum of the ASCII values of the characters in said data file path name and multiplying this sum by a multiplicative factor.

16. The computer based apparatus of claim 12 wherein the external memory comprises an EEPROM.

17. The computer based apparatus of claim 12 wherein the internal memory comprises a static random access memory.

18. The computer based apparatus of claim 12 wherein the computer is a resource limited computer.