From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Matt Armstrong Newsgroups: gmane.emacs.devel Subject: Re: noverlay branch Date: Sat, 08 Oct 2022 20:44:46 -0700 Message-ID: <87wn994q4x.fsf@rfc20.org> References: <87sfjzefvv.fsf@rfc20.org> <875ygt6gbj.fsf@rfc20.org> Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="=-=-=" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="3031"; mail-complaints-to="usenet@ciao.gmane.io" Cc: emacs-devel@gnu.org To: Stefan Monnier Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Sun Oct 09 05:46:02 2022 Return-path: Envelope-to: ged-emacs-devel@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1ohNGL-0000Zu-5o for ged-emacs-devel@m.gmane-mx.org; Sun, 09 Oct 2022 05:46:01 +0200 Original-Received: from localhost ([::1]:36974 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1ohNGI-0001AP-FV for ged-emacs-devel@m.gmane-mx.org; Sat, 08 Oct 2022 23:45:58 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:57206) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1ohNFJ-0000JI-Td for emacs-devel@gnu.org; Sat, 08 Oct 2022 23:44:57 -0400 Original-Received: from relay9-d.mail.gandi.net ([2001:4b98:dc4:8::229]:42779) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1ohNFG-0001cV-7A for emacs-devel@gnu.org; Sat, 08 Oct 2022 23:44:57 -0400 Original-Received: (Authenticated sender: matt@rfc20.org) by mail.gandi.net (Postfix) with ESMTPSA id F16F7FF802; Sun, 9 Oct 2022 03:44:48 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=rfc20.org; s=gm1; t=1665287090; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=aVeDqkKRsB/eTHBsteOhTGNzcJP7lKiTolsIB2X8bjE=; b=XG06+DKR4jnc6CSJBXfgJ7eLF3sPtCncuTHFCfZJoglk2P5xxba0dFiAmDGbzPO/nrxxQn 2Z7/dsguJHLrl17n9URsTjxwvJrK51JiRdVjDcih0VRwACy+2c6zNEDr08xok+aHHWFV5s XA1DS2LmRUciM39e7PhVmf10iPQWp5Z/V4/2eWXiyPg+m69WGTVtdpvFGsE0jTVt9cC9+G 6fwjlfELYsVwo5ZPXpggsiIHw7VshIpWyoell9Qf13DtpShsBWTv3jld6nz5Kogq/u20yL sLJtKsGYtgZ936uRb9SkXcgddZVCRuzoqZtinETKXC7FjNkXtel6W4rM9em2Ag== Original-Received: from matt by naz with local (Exim 4.96) (envelope-from ) id 1ohNF8-005MRi-24; Sat, 08 Oct 2022 20:44:46 -0700 In-Reply-To: <875ygt6gbj.fsf@rfc20.org> Received-SPF: pass client-ip=2001:4b98:dc4:8::229; envelope-from=matt@rfc20.org; helo=relay9-d.mail.gandi.net X-Spam_score_int: -27 X-Spam_score: -2.8 X-Spam_bar: -- X-Spam_report: (-2.8 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_DNSWL_LOW=-0.7, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.29 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-mx.org@gnu.org Original-Sender: "Emacs-devel" Xref: news.gmane.io gmane.emacs.devel:297236 Archived-At: --=-=-= Content-Type: text/plain Matt Armstrong writes: > From 87204feaa4f50744701481f3aa051483647cf9da Mon Sep 17 00:00:00 2001 > From: Matt Armstrong > Date: Sat, 8 Oct 2022 09:15:26 -0700 > Subject: [PATCH 1/2] Comment change: explain inheriting "dirty" offsets > > ; * src/itree.c (interval_generator_next): explain why the code > handles inheriting offsets from dirty nodes. > --- > src/itree.c | 14 +++++++++++--- > 1 file changed, 11 insertions(+), 3 deletions(-) > > diff --git a/src/itree.c b/src/itree.c > index de16af5b0c..1fc711b021 100644 > --- a/src/itree.c > +++ b/src/itree.c > @@ -1086,9 +1086,17 @@ interval_tree_inherit_offset (uintmax_t otick, struct interval_node *node) > node->right->offset += node->offset; > node->offset = 0; > } > - /* FIXME: I wonder when/why this condition can be false, and more generally > - why we'd want to propagate offsets that may not be fully up-to-date. */ > - if (node->parent == ITREE_NULL || node->parent->otick == otick) > + /* FIXME: I wonder when/why this condition can be false, and more > + generally why we'd want to propagate offsets that may not be > + fully up-to-date. --stef > + > + Offsets can be inherited from dirty nodes (with out of date > + otick) during insert and remove. Offsets aren't inherited > + downward from the root for these operations so rotations are > + performed on potentially "dirty" nodes. We could fix this by > + always inheriting offsets downward from the root for every insert > + and remove. --matt > + */ > node->otick = otick; > } Correction to the above patch, where I inadvertently deleted a line of code: --=-=-= Content-Type: text/x-diff Content-Disposition: inline; filename=0001-Comment-change-explain-inheriting-dirty-offsets.patch >From 30f52202775155c1d301af3634d0122c3d7851f8 Mon Sep 17 00:00:00 2001 From: Matt Armstrong Date: Sat, 8 Oct 2022 09:15:26 -0700 Subject: [PATCH 1/3] Comment change: explain inheriting "dirty" offsets ; * src/itree.c (interval_generator_next): explain why the code handles inheriting offsets from dirty nodes. --- src/itree.c | 13 +++++++++++-- 1 file changed, 11 insertions(+), 2 deletions(-) diff --git a/src/itree.c b/src/itree.c index de16af5b0c..05851007f5 100644 --- a/src/itree.c +++ b/src/itree.c @@ -1086,8 +1086,17 @@ interval_tree_inherit_offset (uintmax_t otick, struct interval_node *node) node->right->offset += node->offset; node->offset = 0; } - /* FIXME: I wonder when/why this condition can be false, and more generally - why we'd want to propagate offsets that may not be fully up-to-date. */ + /* FIXME: I wonder when/why this condition can be false, and more + generally why we'd want to propagate offsets that may not be + fully up-to-date. --stef + + Offsets can be inherited from dirty nodes (with out of date + otick) during insert and remove. Offsets aren't inherited + downward from the root for these operations so rotations are + performed on potentially "dirty" nodes. We could fix this by + always inheriting offsets downward from the root for every insert + and remove. --matt + */ if (node->parent == ITREE_NULL || node->parent->otick == otick) node->otick = otick; } -- 2.35.1 --=-=-=--