Mail Archives: cygwin-developers/2002/09/06/12:27:07
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
- Raw text -