From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: 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 464EBBB9C for ; Sun, 4 Dec 2005 17:05:37 +0100 (CET) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id jB4G5ala023887 for ; Sun, 4 Dec 2005 17:05:36 +0100 Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id RAA02342 for ; Sun, 4 Dec 2005 17:05:35 +0100 (MET) Received: from ciao.gmane.org (main.gmane.org [80.91.229.2]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id jB4G5WAs032139 (version=TLSv1/SSLv3 cipher=AES256-SHA bits=256 verify=NO) for ; Sun, 4 Dec 2005 17:05:35 +0100 Received: from list by ciao.gmane.org with local (Exim 4.43) id 1EiwM2-0000YM-Ul for caml-list@inria.fr; Sun, 04 Dec 2005 17:04:46 +0100 Received: from 67.71.25.91 ([67.71.25.91]) by main.gmane.org with esmtp (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Sun, 04 Dec 2005 17:04:46 +0100 Received: from monnier by 67.71.25.91 with local (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Sun, 04 Dec 2005 17:04:46 +0100 X-Injected-Via-Gmane: http://gmane.org/ To: caml-list@inria.fr From: Stefan Monnier Subject: Re: Request for weak functional map ... Date: Sun, 04 Dec 2005 11:03:01 -0500 Message-ID: <878xv0etui.fsf-monnier+gmane.comp.lang.caml.inria@gnu.org> References: <4390B875.3080206@univ-savoie.fr> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Complaints-To: usenet@sea.gmane.org X-Gmane-NNTP-Posting-Host: 67.71.25.91 User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.0.50 (gnu/linux) Cancel-Lock: sha1:liLksLqjI0BdXLPIdKwLyswCHYI= Sender: news X-Miltered: at concorde with ID 439313D0.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at nez-perce with ID 439313CC.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; umontreal:01 logarithmic:01 data:02 tree:02 functional:02 tricky:02 traversal:03 library:03 library:03 complex:04 weak:04 weak:04 structure:04 entries:05 implement:05 X-Spam-Checker-Version: SpamAssassin 3.0.3 (2005-04-27) on yquem.inria.fr X-Spam-Level: * X-Spam-Status: No, score=1.6 required=5.0 tests=RCVD_BY_IP,RCVD_NUMERIC_HELO autolearn=disabled version=3.0.3 > I wish a data structure similar to the Map provided by standard library > (logarithmic insertion and deletion) ... but with a "weak key" behavior: Of course you can implement it in the GC (although it can be tricky if you data-structure is complex, as you mention). But another way to do it is to use a normal non-weak Map but using weak-references for the keys and then "every once in a while" scan the map to remove entries whose weak-key has been collected. If you implement the Map yourself (rather than using the library version), you can do the weak-key-sweep as part of the normal tree traversal done during lookups and insertions. Stefan