From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id TAA19371 for caml-redistribution; Tue, 18 Mar 1997 19:20:25 +0100 (MET) Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id RAA17966 for ; Tue, 18 Mar 1997 17:38:15 +0100 (MET) Received: from hplb.hpl.hp.com (hplb.hpl.hp.com [15.255.59.2]) by concorde.inria.fr (8.7.6/8.7.3) with ESMTP id RAA22481 for ; Tue, 18 Mar 1997 17:37:56 +0100 (MET) Received: from betze.bbn.hp.com by hplb.hpl.hp.com; Tue, 18 Mar 1997 16:37:50 GMT Received: from localhost (localhost [127.0.0.1]) by betze.bbn.hp.com with SMTP (8.7.1/8.7.1) id RAA27735; Tue, 18 Mar 1997 17:37:43 +0100 (MET) Message-Id: <199703181637.RAA27735@betze.bbn.hp.com> X-Authentication-Warning: betze.bbn.hp.com: Host localhost [127.0.0.1] didn't use HELO protocol X-Mailer: exmh version 1.6.4 10/10/95 To: Wolfgang Lux Cc: caml-list@pauillac.inria.fr Subject: Re: Weak pointers In-Reply-To: lux's message of Tue, 18 Mar 1997 16:54:19 +0100. <9703181554.AA46238@idse.heidelbg.ibm.com> X-Face: 7'_lwZ-\~X.Q]-O#D;ju@c|HTi9[>\U8jV5(8sQpm)twOCgN.y]9s:L}A1_]h}_LHF@U5!2 5~FJ"9)`@~BEg9d;ftlb:bj9N>RTv0[VvZe7EMMB:$9hUc]&d9VN? Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: quoted-printable Date: Tue, 18 Mar 1997 16:37:42 +0000 From: Kohler Markus Sender: weis > > [...] > > > 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 | +----------------------------------------------------------------------------+