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: Overlays as an AA-tree Date: Thu, 09 Feb 2017 11:05:46 +0100 Message-ID: <87efz7n0g5.fsf@fastmail.com> 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> <878tpiqiuc.fsf@hochschule-trier.de> <87shnppspb.fsf@hochschule-trier.de> <87o9yc9v30.fsf@hochschule-trier.de> <87a89vaes3.fsf@hochschule-trier.de> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: blaine.gmane.org 1486634797 15559 195.159.176.226 (9 Feb 2017 10:06:37 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Thu, 9 Feb 2017 10:06:37 +0000 (UTC) User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/26.0.50 (berkeley-unix) Cc: Stefan Monnier , emacs-devel@gnu.org To: Andreas Politz Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Thu Feb 09 11:06:32 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 1cblcV-0003hC-OG for ged-emacs-devel@m.gmane.org; Thu, 09 Feb 2017 11:06:31 +0100 Original-Received: from localhost ([::1]:36739 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1cblcb-0001TG-3G for ged-emacs-devel@m.gmane.org; Thu, 09 Feb 2017 05:06:37 -0500 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:47589) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1cblbv-0001Sn-Vv for emacs-devel@gnu.org; Thu, 09 Feb 2017 05:05:57 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1cblbq-0006Zu-Ui for emacs-devel@gnu.org; Thu, 09 Feb 2017 05:05:55 -0500 Original-Received: from out1-smtp.messagingengine.com ([66.111.4.25]:54717) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1cblbq-0006Yl-Jk for emacs-devel@gnu.org; Thu, 09 Feb 2017 05:05:50 -0500 Original-Received: from compute4.internal (compute4.nyi.internal [10.202.2.44]) by mailout.nyi.internal (Postfix) with ESMTP id 8D01520638; Thu, 9 Feb 2017 05:05:48 -0500 (EST) Original-Received: from frontend1 ([10.202.2.160]) by compute4.internal (MEProxy); Thu, 09 Feb 2017 05:05:48 -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=U2I7cUDZrVB0i/vZ8nD8D6dRalI=; b=Q5AJ9x EHwH2+jyb2J67bVsj2ZD04CQ4DPUpk4hTe5xred+GKi4t2Le1GWhGWs3mIdRzeoy H4JGJlBH1UPsgRywzltzDOhJgoNsqac/pa2eqLqPAAoib9Moy8nWSL8uHR0I47HY oPGuOXQdeKtOwZ66hG9beRCt0NuP2JBN8a/xs= 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=U2I7cUDZrVB0i/ vZ8nD8D6dRalI=; b=J1tj30OYDltXDK9uxBlQFtZ4wau/4gbfYIOymW/5Mp281T jvgdTFNYeimQdFrDQ0Q3dL22AzgBt14Lrsz4J2yblVtQQyW+UuDnlR43g4qK0c+a wcjRCsnm269398ZHYHUWnjGrwPE6r9fqhoI0gbAvTe/+/L1obutz+57G4AN2w= X-ME-Sender: X-Sasl-enc: PgI2d9hCTslHto/SXfjTxmCvrkhGttLtbXIrhsGhXFCU 1486634748 Original-Received: from genserv (unknown [5.150.202.248]) by mail.messagingengine.com (Postfix) with ESMTPA id D3DE67E5D1; Thu, 9 Feb 2017 05:05:47 -0500 (EST) In-Reply-To: <87a89vaes3.fsf@hochschule-trier.de> (Andreas Politz's message of "Thu, 09 Feb 2017 10:34:36 +0100") X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] [fuzzy] X-Received-From: 66.111.4.25 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:212158 Archived-At: Andreas Politz writes: > I think, I got mostly everything ready, from Fmake_overlay to > Fbuffer_swap_text. It compiles just fine after which it immediately dumps > core -- but that's another problem. > > I am currently uncertain about how to properly allocate the memory I > need for > > 1. traversing the tree (log(n)) and > 2. storing some nodes (n) > > Number 1. isn't really a problem, since it can be allocated > when an overlay is created and kept for the life-time of the buffer, > since its size is pretty small. > > The other storage I need due to the problem with front-advance overlays > while adjusting the overlays for insert. The size of this thing makes it > not so size to keep around. So, is it save to call xmalloc at this > point ? > I think it should be. I used xmalloc all the time in my branch :) Isn't the idea to gather the interval_nodes which begin at the point of insertion, adjust them outside the tree and then reinsert them? Then you can free the memory right after, no? Why do you need to allocate memory to traverse the tree? Isn't the tree, already there?