Talk:VFS

This is a talk page associated with the Open Source Portal. Changes to all pages like this one can be tracked by watching the "Related Changes" for "Category:Open Source Talk Page"
Please sign comments you leave here by putting four tildes (~~~~) at the end of your comment. For more guidelines, see Talk Page Guidelines

Related discussions:

• OpenClient: Cache operation discussion
• Talk:Texture cache

Alternative implementation

Only desk-checked:

// N_LEVELS * N_CHARS should probably not be greater than 8, since there's a
// separator in the UUID there.
#define N_LEVELS 2
// UUID is hex, so 2 chars means maximum of 256 directories per level
#define N_CHARS 2

#ifdef I_KNOW_THIS_ITS_A_UNIX_SYSTEM
# define DIR_SEP '/'
#else
# define DIR_SEP '\\'
#endif

extern char *cache_dir;
extern int safe_make_directory_path(char *path);

FILE *fopen_texture(char *filename, char *mode)
{
   int l = strlen(cache_dir);
   int m = strlen(filename);
   char *new_filename = calloc(l + 1 + m + N_LEVELS * (N_CHARS + 1) + 1);
   char *s, *t;
   int i, j;
   FILE *fp;

   if (!new_filename) return NULL;

   s = filename;
   t = new_filename;
   strcpy(t, cache_dir);
   t += l;

   for (i = 0; *s && i < N_LEVELS; i++)
   {
     *t++ = DIR_SEP;
     for (j = 0; *s && j < N_CHARS; j++)
       *t++ = *s++;
   }
   *t = '\0';
   if (!safe_make_directory_path(new_filename)) return free(new_filename), NULL;
   *t++ = DIR_SEP;

   strcpy(t, filename);

   fp = fopen(new_filename, mode);
   free(new_filename);
   return fp;
}

VFS index: std::map (low hanging fruit)

I've been reading through the STL source and documentation. std::map by itself is the wrong solution for the index. Strife Onizuka 11:29, 27 March 2007 (PDT)

1. It is only sorted explicitly (std::sort)
2. map.find has a n-based time frame.
   • A cache with 20,000 assets has to do 20,000 comparisons when it wants to find out about the most recently added asset.

Solutions:

1. Sort the map:
   1. Keep the map sorted by doing a binary search to determine where an asset should be inserted.
      • A cache with 20,000 assets would only have to do about 16 comparisons to add an asset
   2. Use std::lower_bound instead of map.find (map.lower_bound suffers from the same problem as map.find)
   Problems:
   • The bulk of the index needs to be written to disk when a single asset is added. mIndexHoles & LLVFS::sync can't be used when adding assets.
2. Keep a duplicated sorted map (without the holes):
   1. All requests into the cache would go through the new map, the old map is used to handle positions and allow for the use of mIndexHoles.
   Problems:
   • Extra resources required for maintaining two maps.