From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Alin Soare Newsgroups: gmane.emacs.devel Subject: Re: line buffer as Red Black Trees instead of linear Date: Thu, 22 May 2014 12:33:29 +0300 Message-ID: References: <83mwein6w1.fsf@gnu.org> <83fvkamg9v.fsf@gnu.org> <837g5mm8ke.fsf@gnu.org> <83ha4jnotl.fsf@gnu.org> <83zjibm5d1.fsf@gnu.org> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary=20cf303f6a003dfe8804f9f9cea0 X-Trace: ger.gmane.org 1400751232 32232 80.91.229.3 (22 May 2014 09:33:52 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Thu, 22 May 2014 09:33:52 +0000 (UTC) Cc: Stefan Monnier , emacs-devel@gnu.org To: Eli Zaretskii Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Thu May 22 11:33:42 2014 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1WnPNd-0000X2-C2 for ged-emacs-devel@m.gmane.org; Thu, 22 May 2014 11:33:41 +0200 Original-Received: from localhost ([::1]:36053 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WnPNc-0002Z1-M9 for ged-emacs-devel@m.gmane.org; Thu, 22 May 2014 05:33:40 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:51725) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WnPNZ-0002Ys-4p for emacs-devel@gnu.org; Thu, 22 May 2014 05:33:37 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1WnPNT-0002eR-7E for emacs-devel@gnu.org; Thu, 22 May 2014 05:33:37 -0400 Original-Received: from mail-ig0-x232.google.com ([2607:f8b0:4001:c05::232]:42386) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WnPNR-0002eB-TM; Thu, 22 May 2014 05:33:29 -0400 Original-Received: by mail-ig0-f178.google.com with SMTP id hl10so3265028igb.11 for ; Thu, 22 May 2014 02:33:29 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=URCuDPkg5sdyMcP7qzcDnMldyqiaBeILipFNftrwgL0=; b=jvUcx9GQ4t0P9W/4NI0jW22BWPdfv/+9XWKxx5rgoyByCEbSd+SNtN72KPjVebA5KL hsXvPQQwoZ181o4xnew6+eHjP2jVSLSxG1QIKy3z5m4/YVkCec+Bl960FwSJ9e15qYVs qXTthUrA66DDJovFKwTyuEjvCHA9eZjyvF9S/2XczPs3Z23imh+3bGfQdIY02e/doF4D AE9HQ5UXztHdn5wOr1d/sYt7zRz9pMklJjUuLk4NqCrd7LFjliDu9iJqsRRORhHHzXw4 HzidPul/qiaVTC7hQf53C41GzjHVMvSL5i2hw1S5+2zrOAw0/+NSP+l3gHqx7rP9ZlW/ 0L8A== X-Received: by 10.42.204.197 with SMTP id fn5mr904285icb.95.1400751209183; Thu, 22 May 2014 02:33:29 -0700 (PDT) Original-Received: by 10.43.142.70 with HTTP; Thu, 22 May 2014 02:33:29 -0700 (PDT) In-Reply-To: <83zjibm5d1.fsf@gnu.org> X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-Received-From: 2607:f8b0:4001:c05::232 X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.14 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-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:172018 Archived-At: --20cf303f6a003dfe8804f9f9cea0 Content-Type: text/plain; charset=UTF-8 > > > > So this means you will also have to rearrange the tree whenever > display properties change, which is more work, and non-trivial one at > that (access to overlay strings is not very efficient in Emacs, when > there are many of them). > > And what happens with text that is covered with an invisible text > property? Does it disappear from the tree? > If you keep a single RBT only for overlays, this tree will be modified only in case of overlay change. And if you have a single property "narrow from X to Y", and inside X and Y there is other property, in the moment when you compute something on this tree, you can simply jump from the node X to the node keeping offset Y. You can ignore what is inside the tree, and the jump is done logarithmically, because searching in RBT is guaranteed to be log in the worse time. Your example shows clearly that it is better to make a separate tree for each class of properties, than keeping text together overlays , together with font locks in the same tree. --20cf303f6a003dfe8804f9f9cea0 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable


So this means you will also have to rearrange the tree whenever
display properties change, which is more work, and non-trivial one at
that (access to overlay strings is not very efficient in Emacs, when
there are many of them).

And what happens with text that is covered with an invisible text
property? =C2=A0Does it disappear from the tree?

If you keep a singl= e RBT only for overlays, this tree will be modified only in case of overlay= change.


And if you have a single property &quo= t;narrow from X to Y", and inside X and Y there is other property, in = the moment when you compute something on this tree, you can simply jump fro= m the node X to the node keeping offset Y. You can ignore what is inside th= e tree, and the jump is done logarithmically, because searching in RBT is g= uaranteed to be log in the worse time.

Your exampl= e shows clearly that it is better to make a separate tree for each class of= properties, than keeping text together overlays , together with font locks= in the same tree.


<= div class=3D"gmail_extra">





--20cf303f6a003dfe8804f9f9cea0--