This is the mail archive of the cygwin-developers@cygwin.com mailing list for the Cygwin project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Contemplating drastic change to mount handling


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@cs.nyu.edu
ZZZzz /,`.-'`'    -.  ;-;;,_		igor@watson.ibm.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


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]