Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #9423 > unrolled thread

Representing a hierarchical file system

Back to article view | Back to comp.lang.c

Contents

  Representing a hierarchical file system jacob navia <jacob@spamsink.net> - 2011-08-15 12:24 +0200
    Re: Representing a hierarchical file system Ian Collins <ian-news@hotmail.com> - 2011-08-15 22:36 +1200
      Re: Representing a hierarchical file system jacob navia <jacob@spamsink.net> - 2011-08-15 19:43 +0200
    Re: Representing a hierarchical file system Keith Thompson <kst-u@mib.org> - 2011-08-15 09:23 -0700
      Re: Representing a hierarchical file system David Thompson <dave.thompson2@verizon.net> - 2011-08-21 03:22 -0400
    Re: Representing a hierarchical file system Nobody <nobody@nowhere.com> - 2011-08-15 18:02 +0100
      Re: Representing a hierarchical file system jacob navia <jacob@spamsink.net> - 2011-08-15 19:44 +0200
    Re: Representing a hierarchical file system China Blue Tip Wrench <chine.bleu@yahoo.com> - 2011-08-15 10:35 -0700
      Re: Representing a hierarchical file system jacob navia <jacob@spamsink.net> - 2011-08-15 19:46 +0200
        Re: Representing a hierarchical file system "Heinrich Wolf" <invalid@invalid.invalid> - 2011-08-15 20:31 +0200
        Re: Representing a hierarchical file system Ian Collins <ian-news@hotmail.com> - 2011-08-16 08:32 +1200
        Re: Representing a hierarchical file system Nobody <nobody@nowhere.com> - 2011-08-16 11:45 +0100
          Re: Representing a hierarchical file system BGB <cr88192@hotmail.com> - 2011-08-16 04:00 -0700

#9423 — Representing a hierarchical file system

Hi

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.

Has this problem been solved in a public available way?

Are there any known implementations?

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 of course incomplete. Are there any available
implementations of such a data structure?

[toc] | [next] | [standalone]

#9424

On 08/15/11 10:24 PM, jacob navia wrote:
> Hi
>
> 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.
>
> Has this problem been solved in a public available way?

I'm not aware of any portable C solutions, but C++ has boost.filesystem 
which may be of interest.

-- 
Ian Collins

[toc] | [prev] | [next] | [standalone]

#9434

Le 15/08/11 12:36, Ian Collins a écrit :
> On 08/15/11 10:24 PM, jacob navia wrote:
>> Hi
>>
>> 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.
>>
>> Has this problem been solved in a public available way?
>
> I'm not aware of any portable C solutions, but C++ has boost.filesystem
> which may be of interest.
>
Thanks, that is very useful

[toc] | [prev] | [next] | [standalone]

#9429

jacob navia <jacob@spamsink.net> writes:
> 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.
[...]

It's not clear that all filesystems can be straightforwardly
represented as "directories and files within a tree structure".
Take a look at OpenVMS, for example -- or Windows, for that matter.

But I suppose you could artificially impose a single-tree structure.

A number of languages provide something like this.  I seem to recall
that there's a Lisp dialect (Scheme?) that has a pretty good portable
filesystem representation.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Nokia
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#9578

On Mon, 15 Aug 2011 09:23:50 -0700, Keith Thompson <kst-u@mib.org>
wrote:

> jacob navia <jacob@spamsink.net> writes:
> > 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.
> [...]
> 
> It's not clear that all filesystems can be straightforwardly
> represented as "directories and files within a tree structure".
> Take a look at OpenVMS, for example -- or Windows, for that matter.
> 
And TENEX/TOPS-20 and Multics, if you can find them.

There are or have been numerous systems that support only one level
directory, and I know one that supports only two levels (exactly), but
those can be treated as restricted cases of tree.

> But I suppose you could artificially impose a single-tree structure.
> 
> A number of languages provide something like this.  I seem to recall
> that there's a Lisp dialect (Scheme?) that has a pretty good portable
> filesystem representation.

Common LISP ca 1994 had a union-of-all-then-known-features thing for
*filenames*. I don't recall that it had anything for a *filesystem*
other than just lists of filenames, and lists of lists, etc.

[toc] | [prev] | [next] | [standalone]

#9430

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).

[toc] | [prev] | [next] | [standalone]

#9435

No, I do not want to implement a file system.

I want some portable representation of a file system structure in memory

[toc] | [prev] | [next] | [standalone]

#9433

In article <j2as5n$4gl$1@speranza.aioe.org>, jacob navia <jacob@spamsink.net> 
wrote:

> typedef struct tagDirectory {
> 	char *Name;
> 	size_t NumberOfChildren;
> 	struct tagDirectory **Subdirs;
> 	size_t NumberOfFiles;
> 	file **Files;
> }Directory;

Unix doesn't distinguish files and subdirectories in a directory. To get that 
you need an additional call for each entry (stat). If you're going to stat, you 
might want to save the information to avoid redundant stat calls. Also the 
directory graph can be cyclic when you follow soft links.

-- 
I remember finding out about you,  | How to loosen bolts with a hammer.
Everyday my mind is all around you,|      I'm whoever you want me to be.
Looking out from my lonely room    | Annoying Usenet one post at a time.
Day after day.                     |   At least I can stay in character.

[toc] | [prev] | [next] | [standalone]

#9437

Le 15/08/11 19:35, China Blue Tip Wrench a écrit :
> In article<j2as5n$4gl$1@speranza.aioe.org>, jacob navia<jacob@spamsink.net>
> wrote:
>
>> typedef struct tagDirectory {
>> 	char *Name;
>> 	size_t NumberOfChildren;
>> 	struct tagDirectory **Subdirs;
>> 	size_t NumberOfFiles;
>> 	file **Files;
>> }Directory;
>
> Unix doesn't distinguish files and subdirectories in a directory. To get that
> you need an additional call for each entry (stat). If you're going to stat, you
> might want to save the information to avoid redundant stat calls. Also the
> directory graph can be cyclic when you follow soft links.
>

I would rather ignore links, and avoid anything Unix specific (or DOS 
specific)

Just a simple hierarchical representation with some attibutes like size
and time

I would like it to be as portable as possible

[toc] | [prev] | [next] | [standalone]

#9439

"jacob navia" <jacob@spamsink.net> schrieb im Newsbeitrag 
news:j2bm0p$14f$3@speranza.aioe.org...
...

> I would rather ignore links, and avoid anything Unix specific (or DOS 
> specific)
>
> Just a simple hierarchical representation with some attibutes like size
> and time
>
> I would like it to be as portable as possible

Be careful!
NTFS also has hard links like Unix, not only *.lnk files 

[toc] | [prev] | [next] | [standalone]

#9451

On 08/16/11 05:46 AM, jacob navia wrote:
> Le 15/08/11 19:35, China Blue Tip Wrench a écrit :
>> In article<j2as5n$4gl$1@speranza.aioe.org>, jacob navia<jacob@spamsink.net>
>> wrote:
>>
>>> typedef struct tagDirectory {
>>> 	char *Name;
>>> 	size_t NumberOfChildren;
>>> 	struct tagDirectory **Subdirs;
>>> 	size_t NumberOfFiles;
>>> 	file **Files;
>>> }Directory;
>>
>> Unix doesn't distinguish files and subdirectories in a directory. To get that
>> you need an additional call for each entry (stat). If you're going to stat, you
>> might want to save the information to avoid redundant stat calls. Also the
>> directory graph can be cyclic when you follow soft links.
>>
>
> I would rather ignore links, and avoid anything Unix specific (or DOS
> specific)
>
> Just a simple hierarchical representation with some attibutes like size
> and time
>
> I would like it to be as portable as possible

Your first and last statements appear contradictory; you can't ignore 
filesystem features and by portable!

I have an application that maintains a directory tree in memory (to 
enable us to search and index 30 million files).  I use is a file object 
and a directory object which is a file with an array of file pointers. 
Following the POSIX model, all meta-data is in the file object.

Because it doesn't care what a directory entry is, the POSIX interface 
is probably the most portable you will find.  Unix/Linux systems can 
access DOS and windows filesystems though the standard interface.

-- 
Ian Collins

[toc] | [prev] | [next] | [standalone]

#9462

On Mon, 15 Aug 2011 19:46:03 +0200, jacob navia wrote:

> I would rather ignore links, and avoid anything Unix specific (or DOS
> specific)
> 
> Just a simple hierarchical representation with some attibutes like size
> and time
> 
> I would like it to be as portable as possible

These are self-contradictory.

If you /really/ ignore links then, on Unix, your filesystem will be empty;
a Unix filesystem is nothing but links. A common Unix noob mistake is
asking how to identify or distinguish a hard link (i.e. something created
by link()) from a "real" file. This is a meaningless question; a hard link
is just a directory entry; the links created by "ln" are no different to
those created when the file itself was originally created with open() or
creat().

You can only create a "hierarchical representation" of a Unix filesystem
by losing the distinction between a (hard) link and the file to which it
refers, so you can't distinguish between N links to a single file and N
distinct files. On the bright side, modern Unices don't normally allow
creating hard links to directories, so you can't have cycles (assuming
that you ignore the "." and ".." links).

If you just discard symbolic links, many filenames will simply be invalid
according to your representation, which is likely to impair its utility.
OTOH, if you treat symbolic links as synonymous with the object to which
they refer, not only will your representation not be hierarchical, it will
probably be cyclic (if you actually manage to construct it without going
into infinite recursion).

[Actually, you can end up going into infinite recursion anyhow, if you try
to traverse a directory tree without explicitly checking for loops, as
directories can be renamed (i.e. moved) at any time.]

If you want portability, you really have to support the key features of
all of the target systems (i.e. the common superset, not the common
subset). So e.g. if you want to support Unix, the data model has to
support the concepts of hard and symbolic links. On Windows, these will
still exist as concepts, but you just won't encounter any in practice.

[toc] | [prev] | [next] | [standalone]

#9464

On 8/16/2011 3:45 AM, Nobody wrote:
> On Mon, 15 Aug 2011 19:46:03 +0200, jacob navia wrote:
>
>> I would rather ignore links, and avoid anything Unix specific (or DOS
>> specific)
>>
>> Just a simple hierarchical representation with some attibutes like size
>> and time
>>
>> I would like it to be as portable as possible
>
> These are self-contradictory.
>
> If you /really/ ignore links then, on Unix, your filesystem will be empty;
> a Unix filesystem is nothing but links. A common Unix noob mistake is
> asking how to identify or distinguish a hard link (i.e. something created
> by link()) from a "real" file. This is a meaningless question; a hard link
> is just a directory entry; the links created by "ln" are no different to
> those created when the file itself was originally created with open() or
> creat().
>
> You can only create a "hierarchical representation" of a Unix filesystem
> by losing the distinction between a (hard) link and the file to which it
> refers, so you can't distinguish between N links to a single file and N
> distinct files. On the bright side, modern Unices don't normally allow
> creating hard links to directories, so you can't have cycles (assuming
> that you ignore the "." and ".." links).
>
> If you just discard symbolic links, many filenames will simply be invalid
> according to your representation, which is likely to impair its utility.
> OTOH, if you treat symbolic links as synonymous with the object to which
> they refer, not only will your representation not be hierarchical, it will
> probably be cyclic (if you actually manage to construct it without going
> into infinite recursion).
>
> [Actually, you can end up going into infinite recursion anyhow, if you try
> to traverse a directory tree without explicitly checking for loops, as
> directories can be renamed (i.e. moved) at any time.]
>
> If you want portability, you really have to support the key features of
> all of the target systems (i.e. the common superset, not the common
> subset). So e.g. if you want to support Unix, the data model has to
> support the concepts of hard and symbolic links. On Windows, these will
> still exist as concepts, but you just won't encounter any in practice.
>

note: on newer Windows one may actually encounter links, as Windows has 
added them and does actually use them for some things.


how I would probably do things:

typedef struct DirEntry_s DirEntry;
typedef struct DirHead_s DirHead;

struct DirEntry_s
{
char *name;
DirHead *dir;	//holds something if a directory
int64_t size;	//file size
...
};

struct DirHead_s
{
DirEntry **ents;	//directory entries
size_t n_files;	//num files in directory
size_t m_files;	//current max size of ents list
...
};

or, alternatively, use a linked list:

struct DirEntry_s
{
DirEntry *next;
char *name;
DirHead *dir;	//holds something if a directory, NULL for file
int64_t size;	//file size
...
};

struct DirHead_s
{
DirEntry *first;	//directory entries
...
};


note that implementing a trivial file-system is not necessarily all that 
much different (although, more common is to have space reserved for the 
filename in-struct and use an endianess-agnostic means of representing 
values, typically so that the dir-ents can map 1:1 with their on-disk 
format, ... but all this is technically optional, and a more filesystem 
agnostic means may have merits as well).

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c

csiph-web