> > [...]
> > > You can use them to implement hash-consing.  Assume you have some tree
> > > data structure.  If you want to share the nodes wherever possible, you
> > > can put every created node into a hash table.  Then when you are about
> > > to create a new node, you first look in the hash table to see if the
> > > same node has already been created.  If this is the case, you return
> > > the old one from the hash table instead of creating a new one.
> > >
> > > But the above prevents the GC from collecting the nodes when they
> > > become unused, because they will always be reachable from the hash
> > > table.  If you use weak pointers in your hash table, the GC will be
> > > able to deallocate the dead nodes, but you still can have access to
> > > the live ones through the weak pointers.
> > >
> >
> > I'm not sure if it makes sense to implement such a tree with weak pointers.
> > To be honest, I think it's not a good idea to do so.
> >
> > The problem is that if you delete an element in the tree it may be that the
> > hash table still points to the node, because there was no garbage collection
> > yet. It could be possible that you would still find the entry troughthe hash
> > table.
>
> Surely this is possible, but I do not see why this should be a problem.
> It will just prevent you from creating an identical copy of an element
> which had been present in the hash table.
>

Ok, in this case it's no problem.

> >
> > IMHO the real solution is to implement a delete method for the tree whcih
> > takes care of all that internal pointers.
> >
>
> No. The delete method for the tree is the wrong place. You would link
> your tree implementation hardly with the use of the hash table and
> disallow the use of the data structure without a hash table or with
> another hash table implementation. This does not seem good software
> engineering practice to me.
>

That's no problem. In some sense this Tree is not a Tree but some kind of
directed graph. This graph datastructure could use a hash table and a tree by
aggregation for example.

There's n reason why this datastructures has to use a specific hash table.

If one deletes a node in graph this means that ALL references to the node hav
to be deleted.

> BTW, in implementing such a method you would have to implement some
> kind of weak pointer yourself.

If I would like to implement reuse of already deleted objects, perhaps
something  similiar would be necessary.

> A data structure might be an element in
> more than one tree so would have to keep reference counts as well to be
> sure that you can remove a data structure from the hash table.


Same argument as above, combining several trees probably means creating a new
datastructure, which should use appropriate delete methods. 
This also has to do with the finalization mechanism. If a finalize method is
called when the object is destroyed, the object could tell all it's depends "
"hey I'm going to be deleted".  This is not directly  related to weak pointers.

>
> I would admit that weak pointers are some dirty kind of feature in the
> language and I'm not quite happy that they. It is very easy to write
> programs in the presence of weak pointers, whose outcome is completly
> random. But in some cases like the one of Damien's example it may be
> the least dirty one.
>
> > By the way, I know what I'm speaking about because we have here an application
> > using the same idea to implement some kind of cache. I does not workproperly
> > because nobody knows at which point of time the garbage collector throws way
> > the objects.
>
> Sure. But this only demonstrates the fact, that you have to use weak
> pointer with care. If you work with objects where a data structure
> which is recreated differs from a data structure that is refetched
> from the cache, weak pointers are really not applicable. (And
> maintaining cache consistency is not trival at all in this case!)

I agree with that point.


Markus

--
+----------------------------------------------------------------------------+
| Markus Kohler                          Hewlett-Packard GmbH                |
| Software Engineer                      Network & System Management Division|
|                                        IT/E Success Team                   |
+----------------------------------------------------------------------------+