Re: Choosing a data structure for cache of multiple fake cursors.

[Keith David Bershatsky]

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 <address@hidden>
> 
> >
> > 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.