A method to reduce media directory search time for directories which may include multiple entries for the same file name.
Original Publication Date: 1999-Nov-01
Included in the Prior Art Database: 2003-Jun-19
Disclosed is a method for greatly reducing the time required to search a media directory which might include multiple entries for the "same" file. For file systems of this type, a "simple" find file "A" necessitates a complete search of the entire directory because finding one entry for file "A" does not satisfy the search requirement. It is necessary to keep searching because normal access requires the most recent version of a file and more entries for "A" could still remain to be found. For example, the High Performace Optical File System (HPOFS) may include multiple entries for one file because it is designed for a write once, read many (WORM) media. To allow a file to be "deleted", another entry is added to the directory indicating that a particular file is to be considered deleted, but there is no actual change to the original directory entry, or the file data already on the media. Should a file of that same name be created again, then another entry would be added to the directory describing the "new" file. The Universal Disk Format (UDF) for Direct View Display (DVD) media also has the possibility of multiple entries for the "same" file name. In this case the multiple entries exist because the file system permits multiple "versions" of the same file. The shortened search hinges on one key observation. With a very minor enhancement, the directory management functions can "know" if multiple entries for one file exist in the media directory. If multiples do not exist, then any directory search can be terminated when the desired file is first found. In practice this means that most directory operations will be reduced by about half. Further, after applying this technique, in most cases the directory appears to be a "normal" re-writable directory with one entry per file. This makes it possible to go on to use other search reduction techniques (such as a form of -buffering- the most recently used directory information to probably reduce subsequent access time) to further reduce the time required. The key to this method is an addition to the functions which provide a list of files (like "dir", or "ls"). Each time a list of files (optionally within some path) is developed, the current path is saved, and a "multiples" flag is intially cleared. Then as each directory entry is found and returned to the requestor a check is added to see if this entry represents a "deleted" file, or a "version" of a file. If either is found, the "multiples" flag is turned on. If at the end of the operation the flag is still off, then there are no multiple entires to worry about, and all subsequent directory search operations (within this same directory) can be stopped when a single match is found. 1