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, 15 May 2014 20:15:14 +0300 Message-ID: References: NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary=001a11c2ab34b9ead604f97370d3 X-Trace: ger.gmane.org 1400174132 10098 80.91.229.3 (15 May 2014 17:15:32 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Thu, 15 May 2014 17:15:32 +0000 (UTC) To: emacs-devel@gnu.org Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Thu May 15 19:15:25 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 1WkzFX-0006xq-V5 for ged-emacs-devel@m.gmane.org; Thu, 15 May 2014 19:15:20 +0200 Original-Received: from localhost ([::1]:59591 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WkzFX-00047a-5W for ged-emacs-devel@m.gmane.org; Thu, 15 May 2014 13:15:19 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:47714) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WkzFU-000473-Oz for emacs-devel@gnu.org; Thu, 15 May 2014 13:15:17 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1WkzFT-0000CZ-Nd for emacs-devel@gnu.org; Thu, 15 May 2014 13:15:16 -0400 Original-Received: from mail-we0-x235.google.com ([2a00:1450:400c:c03::235]:57806) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WkzFT-0000B1-GR for emacs-devel@gnu.org; Thu, 15 May 2014 13:15:15 -0400 Original-Received: by mail-we0-f181.google.com with SMTP id w61so1370785wes.40 for ; Thu, 15 May 2014 10:15:14 -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 :content-type; bh=+VeHL1qSC3mNjbzJR6b6J6+0f7kFDNR+OSjaZgokTyM=; b=JDaf0h3TCUzeGIA+Cd7DDJKQFIocwAVqspAb7yr3uMdfrtHdSTWyM36i54UKUpiBp3 y20zcIRbw53IhwuwPjQZBEJe+Ov5QILnEewNKlhp4Fl3H1uy2YpucKr1tVKh+Em6znon FFOeKiO905G/LyyKWgNt+a2VryAstU2tvJ3+4XqjOKt7Dn9m6AUZKSKTGTPw3FWEcCqy GNtCgkauHAXfGQpnewZMCCCFdjSltDxIkBspH1FuflJ678F2Z/IpMtl7CJTJfzVmYCWh ANO0fX1OPAu/xzUMDOKkYXcg5QBmv6+axyol+LJWczBUmo3VBnbzlH9xPn2k8kVtGTG+ EYow== X-Received: by 10.180.12.135 with SMTP id y7mr9363579wib.39.1400174114628; Thu, 15 May 2014 10:15:14 -0700 (PDT) Original-Received: by 10.194.238.68 with HTTP; Thu, 15 May 2014 10:15:14 -0700 (PDT) In-Reply-To: X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-Received-From: 2a00:1450:400c:c03::235 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:171856 Archived-At: --001a11c2ab34b9ead604f97370d3 Content-Type: text/plain; charset=UTF-8 > > > The whole buffer would be encoded as a list of lines, and each line is > encoded as a red-black tree, as I described. > > This will make fast operations involving the gap, the red-black trees are > quite easy to implement, but I cannot see now the bad side effects involved > by such a change. The major improvement would be the redisplay. > > > As a completion, I want to add that the whole text of a buffer can be kept in a single rbt, and at each node one can add an integer attribute that keeps the number of lines at the left of the node, such that searching for a particular line offset to be done in logarithmic time. All the operations would be in constant or logarithmic time, but the major improvement are the operations on buffer gap, which avoids memory move. --001a11c2ab34b9ead604f97370d3 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable

The whole b= uffer would be encoded as a list of lines, and each line is encoded as a re= d-black tree, as I described.

This will make fast operations involving the gap, the r= ed-black trees are quite easy to implement, but I cannot see now the bad si= de effects involved by such a change. The major improvement would be the re= display.



As a c= ompletion, I want to add that the whole text of a buffer can be kept in a s= ingle rbt, and at each node one can add an integer attribute that keeps the= number of lines at the left of the node, such that searching for a particu= lar line offset to be done in logarithmic time.

All the operations would be in constant or logarithmic = time, but the major improvement are the operations on buffer gap, which avo= ids memory move.



=C2=A0


=C2=A0

=
--001a11c2ab34b9ead604f97370d3--