John Doe
8/15/2011 5:03:00 PM
On Mon, 15 Aug 2011 12:24:56 +0200, jacob navia wrote:
> Within the context of the containers library I would like to be able to
> represent a file system, i.e. directories and files within a tree
> structure.
> For instance:
>
> typedef struct tagFile{
> char *Name;
> size_t size;
> FileTime last_save;
> } file;
>
> typedef struct tagDirectory {
> char *Name;
> size_t NumberOfChildren;
> struct tagDirectory **Subdirs;
> size_t NumberOfFiles;
> file **Files;
> }Directory;
This is quite different to typical filesystems.
E.g. on Unix, you have the inode, which contains the size,
owner, permissions, modified/accessed times, etc, plus the list of blocks
containing the data. Note that the inode /doesn't/ contain the name. Every
file, directory, symlink and device has (or, really, is) an inode. The
stat() call basically returns a copy of the inode, minus information which
is "internal" (e.g. the list of blocks).
Then you have directories, where the data consists of a mapping from names
to inode numbers. On early systems, a directory was simply a list of
<name,inode#> pairs. Modern systems use e.g. a btree to facilitate random
access (looking up a specific name in a directory is far more common than
enumerating the contents of a directory).
DOS' FAT filesystem places everything into the directory, so rather than
just a name and an inode number, the entire "inode" is included as part of
the directory entry. The main drawback compared to Unix is you can't have
hard links (multiple directory entries referring to the same inode
number). Also, on VFAT and NTFS, filenames are Unicode wide strings, not
byte strings. The inefficiencies of FAT are circumvented by building more
efficient representations in memory.
Assuming that you're not trying to implement a real filesystem, I'd
suggest replacing the file and directory structures with a common
"node" structure which includes a union member for the
file/directory/other parts. For a directory, the data would be a map
(btree, hashtable, etc) with names as keys and either nodes or references
(pointers, indices) to nodes. Separate maps for files and subdirectories
may or may not be a good idea.
If you are trying to implement a real filesystem, you need to figure out
how to make modifications efficiently (i.e. not contiguous blocks which
need to be realloc()d whenever something changes).