From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Stefan Monnier Newsgroups: gmane.emacs.devel Subject: Re: [Emacs-diffs] /srv/bzr/emacs/trunk r109512: Inline functions to examine and change buffer overlays. Date: Wed, 08 Aug 2012 14:05:12 -0400 Message-ID: References: <5022934F.3050702@yandex.ru> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: dough.gmane.org 1344449124 18294 80.91.229.3 (8 Aug 2012 18:05:24 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Wed, 8 Aug 2012 18:05:24 +0000 (UTC) Cc: emacs-devel@gnu.org To: Dmitry Antipov Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Wed Aug 08 20:05:23 2012 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 1SzAdF-0007Ad-8e for ged-emacs-devel@m.gmane.org; Wed, 08 Aug 2012 20:05:21 +0200 Original-Received: from localhost ([::1]:37790 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1SzAdD-0004St-Jt for ged-emacs-devel@m.gmane.org; Wed, 08 Aug 2012 14:05:19 -0400 Original-Received: from eggs.gnu.org ([208.118.235.92]:53495) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1SzAdA-0004Sn-V0 for emacs-devel@gnu.org; Wed, 08 Aug 2012 14:05:17 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1SzAd9-0000K6-52 for emacs-devel@gnu.org; Wed, 08 Aug 2012 14:05:16 -0400 Original-Received: from chene.dit.umontreal.ca ([132.204.246.20]:37240) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1SzAd8-0000Ju-VL for emacs-devel@gnu.org; Wed, 08 Aug 2012 14:05:15 -0400 Original-Received: from faina.iro.umontreal.ca (lechon.iro.umontreal.ca [132.204.27.242]) by chene.dit.umontreal.ca (8.14.1/8.14.1) with ESMTP id q78I5C08013083; Wed, 8 Aug 2012 14:05:12 -0400 Original-Received: by faina.iro.umontreal.ca (Postfix, from userid 20848) id B17D2B4081; Wed, 8 Aug 2012 14:05:12 -0400 (EDT) In-Reply-To: <5022934F.3050702@yandex.ru> (Dmitry Antipov's message of "Wed, 08 Aug 2012 20:26:55 +0400") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.1.50 (gnu/linux) X-NAI-Spam-Flag: NO X-NAI-Spam-Threshold: 5 X-NAI-Spam-Score: 0 X-NAI-Spam-Rules: 1 Rules triggered RV4304=0 X-NAI-Spam-Version: 2.2.0.9309 : core <4304> : streams <796337> : uri <1187170> X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 132.204.246.20 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:152346 Archived-At: > I think that it's reasonable to have just one chain of overlays per > buffer, much like the markers and intervals chains per buffer text. Why? The point of having 2 is that they're sorted in opposite order, so that finding overlays close to the division point is faster than O(n). I think the only meaningful improvement for overlays would be to move them to the interval tree, thus replacing the O(n) worst case by an O(log n) worst case for most operations. Stefan