From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED.blaine.gmane.org!not-for-mail From: Stefan Monnier Newsgroups: gmane.emacs.devel Subject: Re: How is text properties stored? Date: Wed, 08 May 2019 20:58:23 -0400 Message-ID: References: <25202F5C-FE09-49D9-8782-5E9D013E0262@gmail.com> Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit Injection-Info: blaine.gmane.org; posting-host="blaine.gmane.org:195.159.176.226"; logging-data="190864"; mail-complaints-to="usenet@blaine.gmane.org" User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/27.0.50 (gnu/linux) To: emacs-devel@gnu.org Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Thu May 09 02:59:13 2019 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([209.51.188.17]) by blaine.gmane.org with esmtps (TLS1.0:RSA_AES_256_CBC_SHA1:256) (Exim 4.89) (envelope-from ) id 1hOXOy-000nTi-Nv for ged-emacs-devel@m.gmane.org; Thu, 09 May 2019 02:59:12 +0200 Original-Received: from localhost ([127.0.0.1]:45811 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1hOXOx-0007UE-HQ for ged-emacs-devel@m.gmane.org; Wed, 08 May 2019 20:59:11 -0400 Original-Received: from eggs.gnu.org ([209.51.188.92]:33769) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1hOXOL-0007Tu-T0 for emacs-devel@gnu.org; Wed, 08 May 2019 20:58:35 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1hOXOK-00086s-UG for emacs-devel@gnu.org; Wed, 08 May 2019 20:58:33 -0400 Original-Received: from [195.159.176.226] (port=52506 helo=blaine.gmane.org) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1hOXOK-000865-IU for emacs-devel@gnu.org; Wed, 08 May 2019 20:58:32 -0400 Original-Received: from list by blaine.gmane.org with local (Exim 4.89) (envelope-from ) id 1hOXOH-000mZz-Tj for emacs-devel@gnu.org; Thu, 09 May 2019 02:58:29 +0200 X-Injected-Via-Gmane: http://gmane.org/ Cancel-Lock: sha1:P6S/I+Tpfxw4N27Kcm6vG0Y5mM0= X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-Received-From: 195.159.176.226 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:236316 Archived-At: > overlays). That’s probably not the case since text property is supposed to > be more efficient than overlays. So how does it work? It's all in src/intervals.[ch]. It starts with: struct interval { /* The first group of entries deal with the tree structure. */ ptrdiff_t total_length; /* Length of myself and both children. */ ptrdiff_t position; /* Cache of interval's character position. */ /* This field is valid in the final target interval returned by find_interval, next_interval, previous_interval and update_interval. It cannot be depended upon in any intermediate intervals traversed by these functions, or any other interval. */ struct interval *left; /* Intervals which precede me. */ struct interval *right; /* Intervals which succeed me. */ /* Parent in the tree, or the Lisp_Object containing this interval tree. */ union { struct interval *interval; Lisp_Object obj; } up; bool_bf up_obj : 1; bool_bf gcmarkbit : 1; /* The remaining components are `properties' of the interval. The first four are duplicates for things which can be on the list, for purposes of speed. */ bool_bf write_protect : 1; /* True means can't modify. */ bool_bf visible : 1; /* False means don't display. */ bool_bf front_sticky : 1; /* True means text inserted just before this interval goes into it. */ bool_bf rear_sticky : 1; /* Likewise for just after it. */ Lisp_Object plist; /* Other properties. */ }; As you can see from the left/right fields, it's a binary tree. And we try to keep it balanced (tho IIRC it's not quite always balanced). Stefan