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, 13 Jan 2017 12:56:15 +0100 Message-ID: <87ziivqilc.fsf@fastmail.com> References: <874m14rnl7.fsf@fastmail.com> <83eg07cr91.fsf@gnu.org> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: blaine.gmane.org 1484308626 9377 195.159.176.226 (13 Jan 2017 11:57:06 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Fri, 13 Jan 2017 11:57:06 +0000 (UTC) User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/26.0.50 (berkeley-unix) Cc: emacs-devel@gnu.org To: Eli Zaretskii Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Fri Jan 13 12:57: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 1cS0TY-0001VL-OD for ged-emacs-devel@m.gmane.org; Fri, 13 Jan 2017 12:56:56 +0100 Original-Received: from localhost ([::1]:40517 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1cS0Tc-0004u0-VK for ged-emacs-devel@m.gmane.org; Fri, 13 Jan 2017 06:57:00 -0500 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:53191) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1cS0T4-0004tv-BR for emacs-devel@gnu.org; Fri, 13 Jan 2017 06:56:27 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1cS0Sz-0006pp-Og for emacs-devel@gnu.org; Fri, 13 Jan 2017 06:56:26 -0500 Original-Received: from out2-smtp.messagingengine.com ([66.111.4.26]:41754) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1cS0Sv-0006nw-RS; Fri, 13 Jan 2017 06:56:17 -0500 Original-Received: from compute4.internal (compute4.nyi.internal [10.202.2.44]) by mailout.nyi.internal (Postfix) with ESMTP id 3B77C20A5A; Fri, 13 Jan 2017 06:56:17 -0500 (EST) Original-Received: from frontend1 ([10.202.2.160]) by compute4.internal (MEProxy); Fri, 13 Jan 2017 06:56:17 -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=zcJ1+idLsz0kX7wYl4n2r3YTJ4Q=; b=5l/Jbl t/sUoCoJddNdinl4L2Pq7jgKywICCwoyKLTQxWBl4FXGp2K7/GG1ujpsB4U7aip8 YcDzbFBensiciw2qnDVUlqi0zIjl5ZBJCKgW/3zLbr1yCF1dW1XR20K4fVTI19NE GIEbb579YIGWT/CxRI1QS4B/cZcvPBC14l3Wo= 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=zcJ1+idLsz0kX7 wYl4n2r3YTJ4Q=; b=hPR5jQ/3cxNPvXHmGGrkuTrg/OBzGKGib4W5WcPGYFT6Y3 bpubR8mIbsHm+NpPPoEz9XudhmrmA3rfuDzl+gYfAkTnm+elxGPukEmeAIxngzc8 6sul9cMbgDHcT6K4iG5jNLJLghRHnNee2aC8b2fI42B+ARCXwAaHm6nx9MARI= X-ME-Sender: X-Sasl-enc: S8vixS3At16FVZ9vOeHVZx2Uwe+KdR0N8+o5e+yyUFiL 1484308576 Original-Received: from genserv (unknown [5.150.202.248]) by mail.messagingengine.com (Postfix) with ESMTPA id 984DF7E1D0; Fri, 13 Jan 2017 06:56:16 -0500 (EST) In-Reply-To: <83eg07cr91.fsf@gnu.org> (Eli Zaretskii's message of "Fri, 13 Jan 2017 10:12:58 +0200") X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] [fuzzy] X-Received-From: 66.111.4.26 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:211243 Archived-At: Eli Zaretskii writes: >> From: Joakim Jalap >> Date: Thu, 12 Jan 2017 22:10:44 +0100 >> >> However the nodes can be updated "externally" from the trees point of >> view. For example if there is a delete in the buffer those overlays >> which were in the deleted portion of the buffer will now be crowded at >> the from_char of the delete. But those could have any address, so they >> will probably be out of order. The problem is how to get them in order >> again. >> >> As far as I've gotten is to gather all the affected nodes (which I think >> are only those of length zero which start (and end) at from_char) into >> an array and sort that. But I can't figure out how to get them into the >> tree again while keeping all the pointers correct. > > This might be a silly idea, but did you try removing them from the > tree, and then re-adding them? (I assume that adding a node will > produce an ordered tree.) Yes, that is the "big hammer" approach :) I hae thought about it, but I think the problem is that it will be too expensive. When I traverse the tree to adjust the overlays for a delete I traverse the whole tree at once (and gather the problematic overlays in an array). If I would remove the problematic overlays instead, I would have to do so with the first one detected (because that's the only time we know the tree is in OK shape). But then the tree might change because of rebalancing, so then I think I would have to restart the adjusting traversal from the root. After all of this I would then have to insert each of the problematic overlays one by one, which is of course also possibly expensive. So I think this approach will be too slow, unfortunately. However, I just had another idea about how to do this (about the 43rd I guess), so I will try that and report back in a few weeks :) Thanks, -- Joakim