Mailing-List: contact cygwin-developers-help AT cygwin DOT com; run by ezmlm
List-Subscribe: <mailto:cygwin-developers-subscribe AT cygwin DOT com>
List-Archive: <http://sources.redhat.com/ml/cygwin-developers/>
List-Post: <mailto:cygwin-developers AT cygwin DOT com>
List-Help: <mailto:cygwin-developers-help AT cygwin DOT com>, <http://sources.redhat.com/ml/#faqs>
Sender: cygwin-developers-owner AT cygwin DOT com
Delivered-To: mailing list cygwin-developers AT cygwin DOT com
X-Authentication-Warning: slinky.cs.nyu.edu: pechtcha owned process doing -bs
Date: Fri, 6 Sep 2002 12:27:03 -0400 (EDT)
From: Igor Pechtchanski <pechtcha AT cs DOT nyu DOT edu>
To: cygwin-developers AT cygwin DOT com
Subject: Re: Contemplating drastic change to mount handling
In-Reply-To: <20020906162124.GK21699@redhat.com>
Message-ID: <Pine.GSO.4.44.0209061225180.7122-100000@slinky.cs.nyu.edu>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII

On Fri, 6 Sep 2002, Christopher Faylor wrote:

> On Sat, Sep 07, 2002 at 02:18:43AM +1000, Robert Collins wrote:
> >On Fri, 2002-09-06 at 13:09, Christopher Faylor wrote:
> >> This thinking came about due to some late night dabbling with tries as a
> >> method for scanning the mount table.  They hold great promise for this
> >> since they are fast and handle maximal matching with ease.  But, then I
> >> was wondering how I could easily store the trie in shared memory since
> >> it relies on pointers and sizing a trie ahead of time essentially
> >> requires building the trie first and then copying it into shared memory
> >> since we don't currently have a convenient method for allocating shared
> >> memory.
> >
> >Why not store the trie in a binary blob in the registry? (I'm just
> >thinking of minimal change needed to get the benefit).
>
> I thought about that but mmaping a file works much nicer.
>
> >I really like the use of tries, I've been meaning to get time to
> >implement that for cygwin for ages. I dont' care either way about
> >/etc/fstab and /etc/mtab.
>
> The big problem with normal tries is their space consumption.  I
> have something hacked together which works around that to some
> degree.
>
> cgf

For sets of long strings with similar prefixes, the PATRICIA tree works
well: http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/PATRICIA.html

You can also use a trie with collapsed non-branching chains...  I suppose
this is what you've hacked together...
	Igor
-- 
				http://cs.nyu.edu/~pechtcha/
      |\      _,,,---,,_		pechtcha AT cs DOT nyu DOT edu
ZZZzz /,`.-'`'    -.  ;-;;,_		igor AT watson DOT ibm DOT com
     |,4-  ) )-,_. ,\ (  `'-'		Igor Pechtchanski
    '---''(_/--'  `-'\_) fL	a.k.a JaguaR-R-R-r-r-r-.-.-.  Meow!

It took the computational power of three Commodore 64s to fly to the moon.
It takes a 486 to run Windows 95.  Something is wrong here. -- SC sig file