Filesystem implementation of Zigzag structure

[Andrew Pam <xanni@xxxxxxxxxxxxxxxxx>]

Filesystem implementation of Zigzag structure
=============================================

Written by and Copyright (c) 5 July 2001 Andrew Pam <xanni@xxxxxxxxxx>

The Zigzag structure can readily be implemented on top of a standard
filesystem with the aid of a reserved or rarely-used separator
character provided that "softlinks" or the equivalent are supported.
In the following examples, the question mark character will be used
as the separator (it may need to be protected from interpretation in
some circumstances, for example command shells).  Words and phrases
contained within angle brackets <> indicate replaceable parameters.
The angle brackets and their contents are not literals.

<filename> represents a Zigzag cell ID
<filename>?+<dimension> and
<filename>?-<dimension> represent a Zigzag connection and may be implemented
	as a pair of softlinks.

Note that the ReiserFS filesystem is particularly well suited to this
implementation of the Zigzag structure due to its high-performance support
for large numbers of small files and large numbers of directory entries.

The traditional filesystem heirarchy can be made visible as Zigzag
structure by implementing <filename>?-contain as a synonym for the
".." filename, <filename>?+contain as a synonym for the first file within
a directory if <filename> is in fact a directory, and <filename>?+embrace
and <filename>?-embrace as the next and previous files within a directory
(wrapping around at the first and last files).

Three potential applications for this implementation are:

1. Floppy disk demo and handheld PDA versions of Zigzag using ReiserFS
   in place of a separate database.

2. A Zigzag "file manager" or "desktop" that can interoperate seamlessly
   with existing operating systems and applications.

3. An extension to existing filesystems that provides the Zigzag semantics
   within the filesystem itself for use by conventional applications.
-- 
mailto:xanni@xxxxxxxxxx                         Andrew Pam
http://www.xanadu.com.au/                       Chief Scientist, Xanadu
http://www.glasswings.com.au/                   Technology Manager, Glass Wings
http://www.sericyb.com.au/sc/                   Manager, Serious Cybernetics
P.O. Box 477, Blackburn VIC 3130 Australia	Phone +61 401 258 915