From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Keith David Bershatsky Newsgroups: gmane.emacs.devel Subject: Re: Choosing a data structure for cache of multiple fake cursors. Date: Tue, 25 Dec 2018 11:21:27 -0800 Message-ID: NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII X-Trace: blaine.gmane.org 1545765581 18223 195.159.176.226 (25 Dec 2018 19:19:41 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Tue, 25 Dec 2018 19:19:41 +0000 (UTC) Cc: emacs-devel@gnu.org To: Eli Zaretskii Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Tue Dec 25 20:19:37 2018 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 1gbsEp-0004bp-Ka for ged-emacs-devel@m.gmane.org; Tue, 25 Dec 2018 20:19:36 +0100 Original-Received: from localhost ([127.0.0.1]:42609 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1gbsGw-0002tT-1c for ged-emacs-devel@m.gmane.org; Tue, 25 Dec 2018 14:21:46 -0500 Original-Received: from eggs.gnu.org ([208.118.235.92]:58672) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1gbsGn-0002tB-FB for emacs-devel@gnu.org; Tue, 25 Dec 2018 14:21:38 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1gbsGi-0007H0-GQ for emacs-devel@gnu.org; Tue, 25 Dec 2018 14:21:37 -0500 Original-Received: from gateway34.websitewelcome.com ([192.185.149.105]:19234) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1gbsGi-0007GA-9O for emacs-devel@gnu.org; Tue, 25 Dec 2018 14:21:32 -0500 Original-Received: from cm16.websitewelcome.com (cm16.websitewelcome.com [100.42.49.19]) by gateway34.websitewelcome.com (Postfix) with ESMTP id 1E65977CD96 for ; Tue, 25 Dec 2018 13:21:29 -0600 (CST) Original-Received: from gator3053.hostgator.com ([50.87.144.69]) by cmsmtp with SMTP id bsGeg0RkJ4FKpbsGegUgLq; Tue, 25 Dec 2018 13:21:29 -0600 X-Authority-Reason: nr=8 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=lawlist.com ; s=default; h=Content-Type:MIME-Version:Subject:Cc:To:From:Message-ID:Date: Sender:Reply-To:Content-Transfer-Encoding:Content-ID:Content-Description: Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID: In-Reply-To:References:List-Id:List-Help:List-Unsubscribe:List-Subscribe: List-Post:List-Owner:List-Archive; bh=wwVbr4TtVpQKHd63alFl8EMJ4pzhvHztcSm1Put3GAs=; b=QRwLqyKpDxzIWHdcvQVLlpMPno 0jZaG/JzoOhHiQU3NCMTGjt0gg9pP9hw96q/BOFdUPvU7OT5MyESeeWtrMlogqmgeHBfvyS9vhHtL nSWWt/vtyXGLKyKXBjGNzqHAAaLuOmyWpI3Hh5RPZdS1Ra70tvyKxKe4P0XBwoXJ5VRrWTGAAbp7f m1kZFXj2yKTX3py6BJ42V0EtADr6FHSxSkRx1CDTE31SxmVmJwyds7568U5dm/hQUNe2Xpw1wuBsl CUUmwbAboDtM3TWRK0HvUit+Mv0E4EjQg1O/rnSbYdDrKTRjXxgXtU2gPxFL3ItcDrQ/Lbec4qkGz PKZs8Nww==; Original-Received: from cpe-45-48-239-195.socal.res.rr.com ([45.48.239.195]:51225 helo=server.local) by gator3053.hostgator.com with esmtpsa (TLSv1:DHE-RSA-AES256-SHA:256) (Exim 4.91) (envelope-from ) id 1gbsGe-003ERO-Bd; Tue, 25 Dec 2018 13:21:28 -0600 X-AntiAbuse: This header was added to track abuse, please include it with any abuse report X-AntiAbuse: Primary Hostname - gator3053.hostgator.com X-AntiAbuse: Original Domain - gnu.org X-AntiAbuse: Originator/Caller UID/GID - [47 12] / [47 12] X-AntiAbuse: Sender Address Domain - lawlist.com X-BWhitelist: no X-Source-IP: 45.48.239.195 X-Source-L: No X-Exim-ID: 1gbsGe-003ERO-Bd X-Source: X-Source-Args: X-Source-Dir: X-Source-Sender: cpe-45-48-239-195.socal.res.rr.com (server.local) [45.48.239.195]:51225 X-Source-Auth: lawlist X-Email-Count: 1 X-Source-Cap: bGF3bGlzdDtsYXdsaXN0O2dhdG9yMzA1My5ob3N0Z2F0b3IuY29t X-Local-Domain: yes X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] [fuzzy] X-Received-From: 192.185.149.105 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:231984 Archived-At: Thank you, Eli, for reading this particular thread. My first thought was to remove elements from the cache, and add elements to the cache. E.g., a Lisp equivalent would be: (setcar (nthcdr 17 the-list) my-variable) or (setcar (nthcdr 17 the-list) my-variable) and (defun remove-nth-element (nth list) (if (zerop nth) (cdr list) (let ((last (nthcdr (1- nth) list))) (setcdr last (cddr last)) list))) (remove-nth-element 0 (list 1 2 3 4 5)) The replace/remove approach above appears to be somewhat daunting given the complexity of the cache described below. Today, I thought of a different approach which is to create a new cache with the desired components. E.g., Loop through the old cache and create a new one that includes new data and omits certain outdated data. That would obviate the need to use the replace/remove approach above. When the fake cursors are active for a particular buffer, each window has its own cache (a Lisp_Object). The cache is a list with three elements: 1. First element of the cache is another list containing lists of 15 elements -- one list of 15 elements is used for each fake cursor. x: A window relative x-axis coordinate for a glyph. fx: A frame relative x-axis coordinate for the vertical bar cursor, which can intersect any desired area of a glyph. This is useful for vertically intersecting nonstandard width characters and also for buffers with variable pitch font. y: A window relative y-axis coordinate for the glyph. fy: A frame relative y-axis coordinate used to align all fake cursors along the horizontal ruler of the crosshairs. hpos: The coordinate within a glyph row used to find a particular glyph of a particular display line. vpos: A particular display line on the y-axis. h: The height of a fake cursor, which is set to the glyph row->visible_height. cursor_type: One of the text_cursor_kinds defined in dispextern.h, with a few additional possible types: NO_FRINGE_BITMAP, LEFT_FRINGE_BITMAP, RIGHT_FRINGE_BITMAP, FRAMED_BOX_CURSOR. cursor_width: The thickness of the horizontal / vertical bar cursors. foreground: The color of a fake cursor in the form of an LSL color vector consisting of three doubles; e.g., a shade of grey is [0.75 0.75 0.75]. The API exposed to the Emacs user lets him/her specify the color in any one of three possible formats: a string such as "grey", a hex format such as "#bfbfbf", or an LSL color vector. If a user specified a string, then Emacs converts it to an LSL color vector. Colors are treated differently on the various platforms, e.g., NS, NT and X11. Depending upon the platform that Emacs was built, the LSL color vector is converted to whatever is needed. background: An LSL color vector (like above), which is used for erasing a fake cursor with that has no glyph. I think of these as floating fake cursors. active_p: A boolean value to indicate whether the fake cursor appears in the active window. minimal_p: A boolean value used to indicate whether the LEFT_FRINGE_BITMAP should be drawn in one of two possible colors. E.g., when the crosshairs and/or the visible fill column are on an idle timer, a blue arrow indicates the timer is pending, and a red arrow is used when the timer fires and the Full Monty is drawn. flavor: Enum values defined in dispextern.h: NO_FLAVOR, MC_GLYPH, MC_GLYPHLESS, MC_OVERLAY_ARROW_BITMAP, MC_PILCROW, MC_HOLLOW_RECTANGLE_RIGHT_ARROW, MC_HOLLOW_RECTANGLE, MC_VERTICAL_BAR_RIGHT_ARROW, MC_VERTICAL_BAR, MC_VERTICAL_BAR_BACKSLASH. These are used to know what type of fake cursor to draw, which may be over a glyph, or floating in thin air, or a particular left/right fringe bitmap. posint: The buffer position of a fake cursor if it coincides with a glyph. 2. The second element of the cache is the window that the cache corresponds to. 3. The third element of the cache is the buffer that the cache corresponds to. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; > Date: [12-25-2018 05:36:26] <25 Dec 2018 15:36:26 +0200> > From: Eli Zaretskii > > > > > The elements of the cache are as follows: x [int]; fx [frame x | int]; y [int]; fy [frame y | int]; hpos [int]; vpos [int]; h [height | int]; cursor_type [int]; cursor_width [int]; foreground [vector of 3 doubles]; background [vector of 3 doubles]; active_p [bool]; minimal_p [bool]; flavor [int]; posint [int]. > > You didn't describe what each element means. > > > In this example, we want to find all VPOS entries in the cache for 5, 8 and 25 and do two things: (i) erase the fake cursors on the line; and, (2) recalculate/redraw the fake cursors on those lines based on the new layout. > > > > Assuming that we are dealing with a potential of 200+ fake cursors on a visible window, what is the best data structure for performance and ease of add/removing elements (with 15 sub-elements)? > > If the number of elements is fixed, then a vector would be more > convenient, but other than that, I don't see why it would be a poor > choice to use a list. We access and modify lists (and other Lisp > objects) from C code all the time, to say nothing of the fact that > these objects and the primitive operations on them are implemented in > C to begin with.