Ayende @ Rahien

Refunds available at head office

Challenge: The directory tree

Since people seems to really enjoy posts like this, here is another one. This time it is an interesting issue that I dealt with today.

Given a set of versioned file, you need to cache them locally. Note that IPersistentCache semantics means that if you put a value in it, is is always going to remain there.

Here is the skeleton:

public interface IPersistentCache
{
	void Set(string key, params string[] items);
	string[] Get(string key);
}

public enum Recursion
{
	None,
	OneLevel,
	Full
}

public class VersionedFile
{
	public int Version;
	public string Name;
}

public class FileSystemCache : IFileSystemCache 
{
	IPersistentCache cache;
	
	public FileSystemCache(IPersistentCache cahce)
	{
		this.cache = cache;
	}
	
	public void Add(VersionedFile[] files)
	{
		// to do
	}

	public string[] ListFilesAndFolders(string root, int version, Recursion recursion)
	{
		// to do
	}
	
}

How would you implement this? Note that your only allowed external dependency is the ICache interface.

The usage is something like this:

// given 
var fsc = new FileSystemCache(cache);
fsc.Add(new []
{
      new VersionFile{Version = 1, Name = "/"},
      new VersionFile{Version = 1, Name = "/foo"},
      new VersionFile{Version = 1, Name = "/foo/bar"},
      new VersionFile{Version = 1, Name = "/foo/bar/text.txt"},
});
fsc.Add(new []
{

      new VersionFile{Version = 2, Name = "/"},
      new VersionFile{Version = 2, Name = "/foo"},
      new VersionFile{Version = 2, Name = "/foo/bar"},
      new VersionFile{Version = 2, Name = "/foo/bar/text.txt"},
      new VersionFile{Version = 2, Name = "/test.txt"},
});

// then 
fsc.ListFilesAndFolders("/", 1, Recursion.None) == { "/" } 

fsc.ListFilesAndFolders("/", 1, Recursion.OneLevel) == { "/", "/foo", } 

fsc.ListFilesAndFolders("/", 2, Recursion.OneLevel) == { "/", "/foo", "test.txt" } 

fsc.ListFilesAndFolders("/", 1, Recursion.Full) == { "/", "/foo", "/foo/bar", "/foo/bar/text.txt"}  

You can assume that all paths are '/' separated and they always starts with '/'.

Comments

Thomas Krause
04/12/2008 11:33 AM by
Thomas Krause

So there is no way I can override a value in IPersistentCache? e.g. I can't do:

cache.Set("a", "test");

cache.Set("a", "nother test");

Without this limitation it should be easier. I use the path to the directory or file to be cached as a key in IPersistentCache and put the path + version to the file as a single item in its value arrays (with some separator like ":"). Then I add the item to the parent directory's item array (again path + version).

Of course adding this item means getting the complete array, building another array and setting this as the new value, which is far from ideal, but you could propably make this more performant by growing the array in larger sizes and setting items in the returned instance directly (if Get doesn't return a clone, but the actual instance of the array).

Another issue with this solution is that you have to enumerate through all versions of files in a directory even if you don't need them.

Other than that the lookup is simply done by getting the values for the path specified in ListFilesAndFolders enumerating them and depending on the recursion mode make further lookups for subdirectories.

Without the possibility to override a value in the cache, you could still simulate something like this with some sort of convention. For example, the first 2 entries are stored in key "PATHNAME", the next 4 are stored in "PATHNAME:2", the next 8 in "PATHNAME:3" ...

But Of course this requires further lookups and is ugly as hell...

Interesting challenge however, I'm excited to see your solution.

Ayende Rahien
04/12/2008 02:57 PM by
Ayende Rahien

Thomas,

Each key have a single unique value.

You can do:

cache.Set("a", "test");

cache.Set("a", "nother test");

and then cache.Get("a") would return "another test".

You are in the right path.

Joshua McKinney
04/12/2008 04:42 PM by
Joshua McKinney

what's your target perf for Add / List? O(?)

Ayende Rahien
04/12/2008 04:45 PM by
Ayende Rahien

O(1), I init the list with the 101 capacity, so it should do no memory alloc

Mark Henke
04/14/2008 05:15 AM by
Mark Henke

I know this does not meet all of your requirements, but to help ease my easily-confused brain, here is a rough draft, unit tested based upon your usage data. Note that when you say "no external dependencies" I assume that means no list processing, and my array experience is weak at best.

public class FileSystemCache : IFileSystemCache

{

    IPersistentCache cache;


    public FileSystemCache(IPersistentCache cache)

    {

        this.cache = cache;

    }


    public void Add(VersionedFile[] files)

    {

        foreach (VersionedFile root in files)

        {

            string[] paths = new string[files.Length];

            int files_processed = 0;


            foreach (VersionedFile child in files)

            {

                if (path_is_root(root, child))

                {

                    paths[files_processed] = child.Name;

                    files_processed++;

                }

            }


            this.cache.Set(get_key(root.Name,root.Version), paths);

        }

    }


    private static bool path_is_root(VersionedFile root, VersionedFile      child)

    {

        return root.Version == child.Version &&    child.Name.Contains(root.Name);

    }


    public string[] ListFilesAndFolders(string root, int version, Recursion recursion)

    {

        string[] files = this.cache.Get( get_key(root, version));

        int max_depth = get_max_depth(files.Length, recursion);

        string[] files_to_return = new string[files.Length];

        int files_processed = 0;


        foreach (string file_path in files)

        {

            if (get_depth(root, file_path) <= max_depth)

            {

                files_to_return[files_processed] = file_path;

                files_processed++;

            }

        }


        return files_to_return;

    }


    private static string get_key(string root, int version)

    {

        return root + ":" + version;

    }


    public int get_depth(string root, string child)

    {

        char[] delimiter = new char[] { '/' };

        return (child.Split(delimiter, StringSplitOptions.RemoveEmptyEntries).Length - root.Split(delimiter, StringSplitOptions.RemoveEmptyEntries).Length);

    }


    private int get_max_depth(int number_of_files, Recursion recursion)

    {

        switch (recursion)

        {

            case Recursion.None:

                return 0;

            case Recursion.OneLevel:

                return 1;

            default:

                return number_of_files;

        }

    }


}
alberto
04/14/2008 08:00 PM by
alberto

I have posted a solution at my website, <a href="http://sharpbites.blogspot.com/2008/04/ayendes-challenge-2-directory-tree.html>here . :)

Comments have been closed on this topic.