From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: * X-Spam-Status: No, score=1.1 required=5.0 tests=AWL,SPF_NEUTRAL autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id 28EF3BC69 for ; Tue, 14 Aug 2007 13:48:20 +0200 (CEST) Received: from nz-out-0506.google.com (nz-out-0506.google.com [64.233.162.234]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id l7EBmINW026751 for ; Tue, 14 Aug 2007 13:48:19 +0200 Received: by nz-out-0506.google.com with SMTP id z3so571682nzf for ; Tue, 14 Aug 2007 04:48:18 -0700 (PDT) DKIM-Signature: a=rsa-sha1; c=relaxed/relaxed; d=gmail.com; s=beta; h=domainkey-signature:received:received:message-id:date:from:to:subject:cc:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references; b=QrFCjjhskuvJuSx16NQq10SSVoKYTDA2xhzdIGBqGxg06kiQxF3IG4Bg2IK6mu3NqOFASVJacIaBmVRC4YJ0xSJcejVMbJv2KmQr8pBFMPuiJo5GLC9ypZC9+NBfmOUH59NV7VSjvK5tciS3E2MsN7cfpieYsJrd8YqT6ovj8bQ= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=beta; h=received:message-id:date:from:to:subject:cc:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references; b=cdD4Pkh1EbRZ3woj0j7COjCZU7shcIgFBz9IJhZxodAaV0GwlUB/M5qH7MKYedz1QNdz/aoYo/OWdqfy3OuuL/Bu+Dw2ZeY3onfVMrqRq6yg83Kpr5l+RKBA0Dd/irjqyA8CvE86CNhmogQRksBStYxtNj1caVMbSmKDbs0V/4k= Received: by 10.142.154.20 with SMTP id b20mr699855wfe.1187092097217; Tue, 14 Aug 2007 04:48:17 -0700 (PDT) Received: by 10.143.168.5 with HTTP; Tue, 14 Aug 2007 04:48:16 -0700 (PDT) Message-ID: <9d3ec8300708140448u4e5664cs4aa0bdc149a9c048@mail.gmail.com> Date: Tue, 14 Aug 2007 13:48:17 +0200 From: "Till Varoquaux" To: "Richard Jones" Subject: Re: [Caml-list] Weak hash table for attaching extra data to an object Cc: caml-list@inria.fr In-Reply-To: <46C18D1B.2070303@functionality.de> MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Content-Disposition: inline References: <20070814101535.GA14485@furbychan.cocan.org> <46C18D1B.2070303@functionality.de> X-j-chkmail-Score: MSGID : 46C19682.001 on concorde : j-chkmail score : X : 0/20 1 0.000 -> 1 X-Miltered: at concorde with ID 46C19682.001 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; hash:01 hashtable:01 browsed:01 lgpl:01 mli:01 cheers:01 node:01 nodes:01 arises:01 algebra:01 hash:01 finalizers:01 beginner's:01 ocaml:01 bug:01 I have a small library that could do the trick. It is built a a hashtable whose keys are weak, you need to recompact it from time to time in order to free associated values. One strategy would be to recompact when n values are freed. I tried to limit the performance cost by storing collision values in a separate table. The code can be browsed online at: http://till.varoquaux.free.fr/projects/mini_js/WeakHt.ml.html There's a very small dependency on another file, i use Option.get (defined as in extlib: let get = function | Some v -> v | None -> raise No_value ) It is licensed under lgpl+special linking clause. If you need a more permissive license let me know. This can be downloaded via darcs: darcs get http://till.varoquaux.free.fr/projects/mini_js/WeakHt.ml.html or directly at: http://till.varoquaux.free.fr/projects/mini_js/WeakHt.ml There no mli file (I'm lazy). Constructive criticism is welcome. If you need automatic collection of values and have a hard time implementing I can work on it. Cheers, Till P.S.: I wasn't aware of HWeak when I did this library, I don't know how it compares performance wise. Having never had to profile this library I actually don't know how bad it really is. This can certainly also be worked on. On 8/14/07, Thomas Fischbacher wrote: > > Richard Jones wrote: > > > I have a module which I can't edit[1]. This module, let's call it > > Document, stores a representation of an XML tree in internal node > > objects: > > > > type intnode > > > > What I want to do is -- completely outside Document -- attach my own > > extra information to these nodes. > > Ah, so the situation really is somewhat common, and not something > just I am running into occasionally. (The problem in particular > also arises occasionally when writing symbolic algebra code when one > wants to attach meta-data (e.g. on typesetting) to terms without > touching the underlying term representations in any way.) > > > The key point is that if the > > garbage collector collects an intnode, then I want my extra > > information to be garbage collected too. > > > > I wonder if anyone has done this, or can suggest a better way to solve > > this problem? The issue of attaching extra data to some existing > > object would seem to be a fairly common one ... > > You might be able to "fake" a weak hash table by using a trick: for a > key-value entry k1 -> v1, you take k1 and v1 and rebuild the outermost > data structure to get k2 with k2 = k1 and k2 != k1 (oh hey, now that > looks confusing, right?), as well as v2 = v1 and v2 != v1. Now, you > enter k2 -> v2 into an ordinary hash table and register finalizers for > k1 and v1 which remove this k2 -> v2 entry from your hash. That might > do. > > -- > best regards, > Thomas Fischbacher > tf@functionality.de > > _______________________________________________ > Caml-list mailing list. Subscription management: > http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list > Archives: http://caml.inria.fr > Beginner's list: http://groups.yahoo.com/group/ocaml_beginners > Bug reports: http://caml.inria.fr/bin/caml-bugs > -- http://till-varoquaux.blogspot.com/