From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Andreas Politz Newsgroups: gmane.emacs.devel Subject: Re: Overlays as an AA-tree Date: Mon, 06 Feb 2017 18:32:54 +0100 Message-ID: <87y3xjdy2h.fsf@hochschule-trier.de> References: <87d1jylv43.fsf@fastmail.com> <87fujv64mn.fsf@hochschule-trier.de> <87fujvpkzc.fsf@fastmail.com> <87vasr5tqd.fsf@hochschule-trier.de> <87d1ex4kon.fsf@hochschule-trier.de> <87d1evod6x.fsf@fastmail.com> <877f53ftab.fsf@hochschule-trier.de> <878tpjnxkt.fsf@fastmail.com> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: blaine.gmane.org 1486402483 3263 195.159.176.226 (6 Feb 2017 17:34:43 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Mon, 6 Feb 2017 17:34:43 +0000 (UTC) User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.1 (gnu/linux) Cc: Stefan Monnier , emacs-devel@gnu.org To: Joakim Jalap Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Mon Feb 06 18:34:39 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 1canBX-0000Zb-7n for ged-emacs-devel@m.gmane.org; Mon, 06 Feb 2017 18:34:39 +0100 Original-Received: from localhost ([::1]:49842 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1canBb-0003v5-6K for ged-emacs-devel@m.gmane.org; Mon, 06 Feb 2017 12:34:43 -0500 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:45306) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1canA8-0003sc-Oj for emacs-devel@gnu.org; Mon, 06 Feb 2017 12:33:16 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1canA5-0006Np-Kr for emacs-devel@gnu.org; Mon, 06 Feb 2017 12:33:12 -0500 Original-Received: from gateway-a.fh-trier.de ([143.93.54.181]:60462) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1canA5-0006NY-Al for emacs-devel@gnu.org; Mon, 06 Feb 2017 12:33:09 -0500 X-Virus-Scanned: by Amavisd-new + McAfee uvscan + ClamAV [Rechenzentrum Hochschule Trier (RZ/HT)] Original-Received: from localhost (ip5f5bdfbc.dynamic.kabel-deutschland.de [95.91.223.188]) (using TLSv1 with cipher AES256-SHA (256/256 bits)) (No client certificate requested) (Authenticated sender: politza) by gateway-a.fh-trier.de (Postfix) with ESMTPSA id D6F7D179AC01; Mon, 6 Feb 2017 18:32:54 +0100 (CET) DKIM-Signature: v=1; a=rsa-sha1; c=simple/simple; d=hochschule-trier.de; s=default; t=1486402374; bh=qxs2PwoT9Lav5Dy7uGtRDCUzYcQ=; h=From:To:Cc:Subject:References:Date:In-Reply-To:Message-ID: MIME-Version:Content-Type; b=ZOFPVWaYl9He19JvvT6buelSAqODTb8/42+aPlOgwlMCiTQ0sKjlJoJwzCDk8cjCr 8jd5ccmZjyOCS4hx5mma/wNvquFGWwh5C9enDVrkqDIkGeLbTtGLTj6P7Zu9HFzkXY GQkDB4/MnnchwASV/GRDJu5J4eS0jR0hAeoqeCRw= In-Reply-To: <878tpjnxkt.fsf@fastmail.com> (Joakim Jalap's message of "Mon, 06 Feb 2017 16:33:22 +0100") X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6.x [fuzzy] X-Received-From: 143.93.54.181 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:212048 Archived-At: Joakim Jalap writes: > I don't think it would be that ugly. Instead of: > > adjust_overlays_for_insert (current_buffer->overlays); > > it will be: > > adjust_overlays_for_insert (current_buffer->front_insert_overlays); > adjust_overlays_for_insert (current_buffer->non_front_insert_overlays); > Well, maybe ugly is not the right word. Take at the current code (where overlays are split into 2 lists), were you see frequent occurrences of paired loops etc.. But first, you're not done. You also need to merge two lists from both trees sometimes, e.g. if you are looking for the next overlay after some position. More generally, if the overlays need to be in order. Secondly, the code which fixes the tree is pretty compact (~10lines) and in the worst case (all but one overlay need to be reinserted) the run-time is at most doubled, I think. But two times little is still not very much (compared to the status quo anyway) and we spare ourselves above trouble. -ap