From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Joakim Jalap Newsgroups: gmane.emacs.devel Subject: Re: Overlay tree. Stuck again Date: Fri, 03 Feb 2017 13:35:06 +0100 Message-ID: <87bmujpi4l.fsf@fastmail.com> References: <874m14rnl7.fsf@fastmail.com> <83eg07cr91.fsf@gnu.org> <87ziivqilc.fsf@fastmail.com> <87poizsmpb.fsf@hochschule-trier.de> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: blaine.gmane.org 1486125487 4967 195.159.176.226 (3 Feb 2017 12:38:07 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Fri, 3 Feb 2017 12:38:07 +0000 (UTC) User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/26.0.50 (berkeley-unix) Cc: emacs-devel@gnu.org To: Andreas Politz Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Fri Feb 03 13:38:02 2017 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1cZd7p-00010Q-C3 for ged-emacs-devel@m.gmane.org; Fri, 03 Feb 2017 13:38:01 +0100 Original-Received: from localhost ([::1]:33884 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1cZd7t-0006Ul-DW for ged-emacs-devel@m.gmane.org; Fri, 03 Feb 2017 07:38:05 -0500 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:58671) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1cZd56-00049Y-Ua for emacs-devel@gnu.org; Fri, 03 Feb 2017 07:35:14 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1cZd53-0002wK-1s for emacs-devel@gnu.org; Fri, 03 Feb 2017 07:35:13 -0500 Original-Received: from out1-smtp.messagingengine.com ([66.111.4.25]:36075) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1cZd52-0002um-Sm for emacs-devel@gnu.org; Fri, 03 Feb 2017 07:35:09 -0500 Original-Received: from compute4.internal (compute4.nyi.internal [10.202.2.44]) by mailout.nyi.internal (Postfix) with ESMTP id 1767720892; Fri, 3 Feb 2017 07:35:08 -0500 (EST) Original-Received: from frontend1 ([10.202.2.160]) by compute4.internal (MEProxy); Fri, 03 Feb 2017 07:35:08 -0500 DKIM-Signature: v=1; a=rsa-sha1; c=relaxed/relaxed; d=fastmail.com; h=cc :content-type:date:from:in-reply-to:message-id:mime-version :references:subject:to:x-me-sender:x-me-sender:x-sasl-enc :x-sasl-enc; s=mesmtp; bh=cYCoUose1QftJPj7CltX7C4cDks=; b=E6HNlg 8KPCUHtCLGJYz6LT3c0KkbvzaaD4hKudj+qNGT/51HIkCSDtXUBMR0W3cCsPAet+ OIeFnHPvMfSneuDRwvsdzD4pSOXY048S+Rcp2VHZWpY+hzCuysRo9j6+bixCSJ1d jKT2f+eMwyfRTd7QHyYCA/agpO7qQ9Sux0XhY= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed/relaxed; d= messagingengine.com; h=cc:content-type:date:from:in-reply-to :message-id:mime-version:references:subject:to:x-me-sender :x-me-sender:x-sasl-enc:x-sasl-enc; s=smtpout; bh=cYCoUose1QftJP j7CltX7C4cDks=; b=UJUeAPBeU/vo2dt3EQ58IlYWppXd/avU1qqV7sK3P9uva2 MnyqVv91Q5HofAnxGEzMidq9ISN8B/2RBUYBuDiZX/Y3dpycoplKlWvb8tCnVELl 7jCe79PYm5z89XAqHgJFzfURi7osE1JiSILieRwSQLDpBpN0ngAINARjl3g9g= X-ME-Sender: X-Sasl-enc: ktPE3LoW94guH3afi6Z7bQRkOEfm9qWd7TG/ejfwroVr 1486125307 Original-Received: from genserv (unknown [5.150.202.248]) by mail.messagingengine.com (Postfix) with ESMTPA id 7845D7E21D; Fri, 3 Feb 2017 07:35:07 -0500 (EST) In-Reply-To: <87poizsmpb.fsf@hochschule-trier.de> (Andreas Politz's message of "Fri, 03 Feb 2017 09:28:00 +0100") X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] [fuzzy] X-Received-From: 66.111.4.25 X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.21 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Original-Sender: "Emacs-devel" Xref: news.gmane.org gmane.emacs.devel:211926 Archived-At: Andreas Politz writes: > Joakim Jalap writes: > >> Eli Zaretskii writes: >>> [...] try removing them from the tree, and then re-adding them [...] >> >> Yes, that is the "big hammer" approach :) I hae thought about it, but I >> think the problem is that it will be too expensive. [...] > > Joakim, I think that trying to somehow manually fix the disorder is at > least as expensive as a deletion and reinsertion. Because if it weren't > you would have essentially discovered a better algorithm for balancing > trees then the one you've got. Well this case isn't really about rebalncing, since the tree was balanced to begin with, and no nodes are deleted or inserted. The problem is that a few overlays end up in the wrong place in the tree since I sort by different criteria (memory address) than before for those overlays which happened to end up with the same start/end. > The trick is probably to gather the dirty nodes in post-order and delete > them all at once. This way you're only removing a node, if its > corresponding sub-tree is in order. After that you're free to reinsert > them again. Yes, that should do it. But that would be many traversals of the tree, so I'm afraid it would be too slow. Anyway, I'm trying a new approach now, where the tree is separate from the acual struct Lisp_Overlays, but each overlay is linked to a node in the tree with a pointer (and vice versa). I think this might be easier (that's my theory at least). > > -ap -- Joakim