Choosing a data structure for cache of multiple fake cursors.

[Keith David Bershatsky]

I am working on optimizing the drawing/erasing of multiple fake cursors in 
conjunction with the proposed implementation of feature requests #22873 
(multiple fake cursors) and #17684 (crosshairs / visible fill-column).

The lines that need to potentially be updated can be extracted from 
update_window, which calls update_window_line, which calls update_text_area.  I 
have created modified versions of update_window_line / update_text_area and 
made a "dry run" that yields a list of lines that need to potentially be 
updated (before the updating actually occurs).  Let us assume for purposes of 
this example that the "dry run" tells us that we need to potentially update 
VPOS lines 5, 8 and 25.

The cache of multiple fake cursors is presently in the form of a Lisp_Object 
with 15 elements for each fake cursor.  From studying the Emacs code, it 
appears that a Lisp_Object may have been a poor choice for the cache data 
structure.  The reason I say that, is because now I am faced with the need to 
add/delete certain elements from the cache.

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].

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)?

EXAMPLE:  Remove all lines from the cache that have a VPOS of 5, 8 and 25; and, 
add new entries to the cache with updated values for lines with a VPOS of 5, 8 
and 25.

Thanks,

Keith