[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
scratch/text-index d0a9025fc6f 2/8: marker.c: Keep markers in arrays rat
|
From: |
Stefan Monnier |
|
Subject: |
scratch/text-index d0a9025fc6f 2/8: marker.c: Keep markers in arrays rather than linked lists |
|
Date: |
Wed, 23 Apr 2025 01:55:47 -0400 (EDT) |
branch: scratch/text-index
commit d0a9025fc6fd998fbce4d9dd1e1674c07edf47ef
Author: Gerd Möllmann <gerd.moellmann@gmail.com>
Commit: Stefan Monnier <monnier@iro.umontreal.ca>
marker.c: Keep markers in arrays rather than linked lists
* src/marker.c (attach_marker): Use `marker_vector_add`.
(unchain_marker): Rewrite.
* src/pdumper.c (dump_marker): Handle new field `entry`.
(dump_buffer): Adjust code for `markers` field.
* src/lisp.h (gc_vsize): New function.
(gc_asize): Use it.
(struct Lisp_Marker): Delete `next` field, add field `entry` instead.
* src/alloc.c (Fmake_marker): Don't initialize `next`.
* src/undo.c (record_marker_adjustments):
* src/insdel.c (adjust_markers_for_delete, adjust_markers_for_insert)
(adjust_markers_for_replace, adjust_markers_bytepos):
* src/coding.c (decode_coding_object, encode_coding_object):
* src/editfns.c (transpose_markers): Use `DO_MARKERS`.
* src/buffer.h (struct buffer_text): Change type of `markers` field.
---
src/Makefile.in | 1 +
src/alloc.c | 41 +++++---
src/buffer.c | 78 +++++++-------
src/buffer.h | 12 +--
src/coding.c | 89 ++++++++--------
src/editfns.c | 4 +-
src/insdel.c | 19 ++--
src/lisp.h | 18 ++--
src/marker-vector.c | 293 ++++++++++++++++++++++++++++++++++++++++++++++++++++
src/marker-vector.h | 70 +++++++++++++
src/marker.c | 40 +------
src/pdumper.c | 7 +-
src/undo.c | 3 +-
13 files changed, 504 insertions(+), 171 deletions(-)
diff --git a/src/Makefile.in b/src/Makefile.in
index 451e047162a..d6f4893ce49 100644
--- a/src/Makefile.in
+++ b/src/Makefile.in
@@ -464,6 +464,7 @@ base_obj = dispnew.o frame.o scroll.o xdisp.o menu.o
$(XMENU_OBJ) window.o \
profiler.o decompress.o \
thread.o systhread.o sqlite.o treesit.o \
itree.o json.o \
+ marker-vector.o
\
$(MSDOS_OBJ) $(MSDOS_X_OBJ) $(NS_OBJ) $(CYGWIN_OBJ) $(FONT_OBJ) \
$(W32_OBJ) $(WINDOW_SYSTEM_OBJ) $(XGSELOBJ) \
$(HAIKU_OBJ) $(PGTK_OBJ) $(ANDROID_OBJ)
diff --git a/src/alloc.c b/src/alloc.c
index 07ca8474bf3..8c169accf88 100644
--- a/src/alloc.c
+++ b/src/alloc.c
@@ -3809,7 +3809,6 @@ DEFUN ("make-marker", Fmake_marker, Smake_marker, 0, 0, 0,
p->buffer = 0;
p->bytepos = 0;
p->charpos = 0;
- p->next = NULL;
p->insertion_type = 0;
p->need_adjustment = 0;
return make_lisp_ptr (p, Lisp_Vectorlike);
@@ -3834,8 +3833,7 @@ build_marker (struct buffer *buf, ptrdiff_t charpos,
ptrdiff_t bytepos)
m->bytepos = bytepos;
m->insertion_type = 0;
m->need_adjustment = 0;
- m->next = BUF_MARKERS (buf);
- BUF_MARKERS (buf) = m;
+ marker_vector_add (buf, m);
return make_lisp_ptr (m, Lisp_Vectorlike);
}
@@ -6264,6 +6262,13 @@ mark_buffer (struct buffer *buffer)
mark_interval_tree (buffer_intervals (buffer));
+ /* Mark the marker vector itself live, but don't process its contents
+ yet, because these are weak references. The marker vector can
+ already have been set to nil in kill-buffer. */
+ Lisp_Object mv = BUF_MARKERS (buffer);
+ if (!NILP (mv))
+ set_vector_marked (XVECTOR (mv));
+
/* For now, we just don't mark the undo_list. It's done later in
a special way just before the sweep phase, and after stripping
some of its elements that are not needed any more.
@@ -6271,7 +6276,7 @@ mark_buffer (struct buffer *buffer)
for dead buffers, the undo_list should be nil (set by Fkill_buffer),
but just to be on the safe side, we mark it here. */
if (!BUFFER_LIVE_P (buffer))
- mark_object (BVAR (buffer, undo_list));
+ mark_object (BVAR (buffer, undo_list));
if (!itree_empty_p (buffer->overlays))
mark_overlays (buffer->overlays->root);
@@ -7103,21 +7108,23 @@ sweep_symbols (void)
gcstat.total_free_symbols = num_free;
}
-/* Remove BUFFER's markers that are due to be swept. This is needed since
- we treat BUF_MARKERS and markers's `next' field as weak pointers. */
+/* Remove BUFFER's markers that are due to be swept. This is needed
+ since we treat marker references from BUF_MARKER weak references.
+ This relies on the fact that marker vectors only contain markers,
+ fixnums and nil, which means we only have to look at the marker
+ slots. If such a marker is not yet marked, it's dead and we remove
+ it from the marker vector. If it is not dead, it won't be freed
+ my sweep_vectors which is called after sweep_buffers. */
+
static void
-unchain_dead_markers (struct buffer *buffer)
+unchain_dead_markers (struct buffer *b)
{
- struct Lisp_Marker *this, **prev = &BUF_MARKERS (buffer);
-
- while ((this = *prev))
- if (vectorlike_marked_p (&this->header))
- prev = &this->next;
- else
- {
- this->buffer = NULL;
- *prev = this->next;
- }
+ DO_MARKERS (b, m)
+ {
+ if (!vectorlike_marked_p (&m->header))
+ marker_vector_remove (XVECTOR (BUF_MARKERS (b)), m);
+ }
+ END_DO_MARKERS;
}
NO_INLINE /* For better stack traces */
diff --git a/src/buffer.c b/src/buffer.c
index 6d066aa304d..ea80ad91887 100644
--- a/src/buffer.c
+++ b/src/buffer.c
@@ -618,6 +618,8 @@ even if it is dead. The return value is never nil. */)
b->begv_byte = BEG_BYTE;
b->zv_byte = BEG_BYTE;
+ BUF_MARKERS (b) = make_marker_vector ();
+
BUF_GPT (b) = BEG;
BUF_GPT_BYTE (b) = BEG_BYTE;
@@ -661,8 +663,6 @@ even if it is dead. The return value is never nil. */)
reset_buffer_local_variables (b, 1);
bset_mark (b, Fmake_marker ());
- BUF_MARKERS (b) = NULL;
-
/* Put this in the alist of all live buffers. */
XSETBUFFER (buffer, b);
Vbuffer_alist = nconc2 (Vbuffer_alist, list1 (Fcons (name, buffer)));
@@ -1894,7 +1894,6 @@ cleaning up all windows currently displaying the buffer
to be killed. */)
Lisp_Object buffer;
struct buffer *b;
Lisp_Object tem;
- struct Lisp_Marker *m;
if (NILP (buffer_or_name))
buffer = Fcurrent_buffer ();
@@ -2077,18 +2076,14 @@ cleaning up all windows currently displaying the buffer
to be killed. */)
/* Unchain all markers that belong to this indirect buffer.
Don't unchain the markers that belong to the base buffer
or its other indirect buffers. */
- struct Lisp_Marker **mp = &BUF_MARKERS (b);
- while ((m = *mp))
+ DO_MARKERS (b, m)
{
if (m->buffer == b)
- {
- m->buffer = NULL;
- *mp = m->next;
- }
- else
- mp = &m->next;
+ marker_vector_remove (XVECTOR (BUF_MARKERS (b)), m);
}
- /* Intervals should be owned by the base buffer (Bug#16502). */
+ END_DO_MARKERS;
+
+ /* Intervals should be owned by the base buffer (Bug#16502). */
i = buffer_intervals (b);
if (i)
{
@@ -2101,14 +2096,7 @@ cleaning up all windows currently displaying the buffer
to be killed. */)
{
/* Unchain all markers of this buffer and its indirect buffers.
and leave them pointing nowhere. */
- for (m = BUF_MARKERS (b); m; )
- {
- struct Lisp_Marker *next = m->next;
- m->buffer = 0;
- m->next = NULL;
- m = next;
- }
- BUF_MARKERS (b) = NULL;
+ marker_vector_reset (b);
set_buffer_intervals (b, NULL);
/* Perhaps we should explicitly free the interval tree here... */
@@ -2633,22 +2621,28 @@ results, see Info node `(elisp)Swapping Text'. */)
other_buffer->text->end_unchanged = other_buffer->text->gpt;
swap_buffer_overlays (current_buffer, other_buffer);
{
- struct Lisp_Marker *m;
- for (m = BUF_MARKERS (current_buffer); m; m = m->next)
- if (m->buffer == other_buffer)
- m->buffer = current_buffer;
- else
- /* Since there's no indirect buffer in sight, markers on
- BUF_MARKERS(buf) should either be for `buf' or dead. */
- eassert (!m->buffer);
- for (m = BUF_MARKERS (other_buffer); m; m = m->next)
- if (m->buffer == current_buffer)
- m->buffer = other_buffer;
- else
- /* Since there's no indirect buffer in sight, markers on
- BUF_MARKERS(buf) should either be for `buf' or dead. */
- eassert (!m->buffer);
+ DO_MARKERS (current_buffer, m)
+ {
+ if (m->buffer == other_buffer)
+ m->buffer = current_buffer;
+ else
+ /* Since there's no indirect buffer in sight, markers on
+ BUF_MARKERS(buf) should either be for `buf' or dead. */
+ eassert (!m->buffer);
+ }
+ END_DO_MARKERS;
+ DO_MARKERS (other_buffer, m)
+ {
+ if (m->buffer == current_buffer)
+ m->buffer = other_buffer;
+ else
+ /* Since there's no indirect buffer in sight, markers on
+ BUF_MARKERS(buf) should either be for `buf' or dead. */
+ eassert (!m->buffer);
+ }
+ END_DO_MARKERS;
}
+
{ /* Some of the C code expects that both window markers of a
live window points to that window's buffer. So since we
just swapped the markers between the two buffers, we need
@@ -2710,7 +2704,6 @@ If the multibyte flag was really changed, undo
information of the
current buffer is cleared. */)
(Lisp_Object flag)
{
- struct Lisp_Marker *tail, *markers;
Lisp_Object btail, other;
ptrdiff_t begv, zv;
bool narrowed = (BEG != BEGV || Z != ZV);
@@ -2756,9 +2749,11 @@ current buffer is cleared. */)
GPT = GPT_BYTE;
TEMP_SET_PT_BOTH (PT_BYTE, PT_BYTE);
-
- for (tail = BUF_MARKERS (current_buffer); tail; tail = tail->next)
- tail->charpos = tail->bytepos;
+ DO_MARKERS (current_buffer, tail)
+ {
+ tail->charpos = tail->bytepos;
+ }
+ END_DO_MARKERS;
/* Convert multibyte form of 8-bit characters to unibyte. */
pos = BEG;
@@ -2908,13 +2903,12 @@ current buffer is cleared. */)
TEMP_SET_PT_BOTH (position, byte);
}
- tail = markers = BUF_MARKERS (current_buffer);
-
- for (; tail; tail = tail->next)
+ DO_MARKERS (current_buffer, tail)
{
tail->bytepos = advance_to_char_boundary (tail->bytepos);
tail->charpos = BYTE_TO_CHAR (tail->bytepos);
}
+ END_DO_MARKERS;
/* Do this last, so it can calculate the new correspondences
between chars and bytes. */
diff --git a/src/buffer.h b/src/buffer.h
index 6f817c6dd61..55f3b457939 100644
--- a/src/buffer.h
+++ b/src/buffer.h
@@ -274,14 +274,8 @@ struct buffer_text
/* Properties of this buffer's text. */
INTERVAL intervals;
- /* The markers that refer to this buffer.
- This is actually a single marker ---
- successive elements in its marker `chain'
- are the other markers referring to this buffer.
- This is a singly linked unordered list, which means that it's
- very cheap to add a marker to the list and it's also very cheap
- to move a marker within a buffer. */
- struct Lisp_Marker *markers;
+ /* Marker vector. */
+ Lisp_Object markers;
/* Usually false. Temporarily true in decode_coding_gap to
prevent Fgarbage_collect from shrinking the gap and losing
@@ -1750,4 +1744,6 @@ INLINE_HEADER_END
int compare_overlays (const void *v1, const void *v2);
void make_sortvec_item (struct sortvec *item, Lisp_Object overlay);
+#include "marker-vector.h"
+
#endif /* EMACS_BUFFER_H */
diff --git a/src/coding.c b/src/coding.c
index 63b0dbeb18b..c38fcabd0b9 100644
--- a/src/coding.c
+++ b/src/coding.c
@@ -8118,14 +8118,13 @@ decode_coding_object (struct coding_system *coding,
move_gap_both (from, from_byte);
if (BASE_EQ (src_object, dst_object))
{
- struct Lisp_Marker *tail;
-
- for (tail = BUF_MARKERS (current_buffer); tail; tail = tail->next)
+ DO_MARKERS (current_buffer, tail)
{
tail->need_adjustment
= tail->charpos == (tail->insertion_type ? from : to);
need_marker_adjustment |= tail->need_adjustment;
}
+ END_DO_MARKERS;
saved_pt = PT, saved_pt_byte = PT_BYTE;
TEMP_SET_PT_BOTH (from, from_byte);
current_buffer->text->inhibit_shrinking = true;
@@ -8250,25 +8249,26 @@ decode_coding_object (struct coding_system *coding,
if (need_marker_adjustment)
{
- struct Lisp_Marker *tail;
-
- for (tail = BUF_MARKERS (current_buffer); tail; tail = tail->next)
- if (tail->need_adjustment)
- {
- tail->need_adjustment = 0;
- if (tail->insertion_type)
- {
- tail->bytepos = from_byte;
- tail->charpos = from;
- }
- else
- {
- tail->bytepos = from_byte + coding->produced;
- tail->charpos
- = (NILP (BVAR (current_buffer,
enable_multibyte_characters))
- ? tail->bytepos : from + coding->produced_char);
- }
- }
+ DO_MARKERS (current_buffer, tail)
+ {
+ if (tail->need_adjustment)
+ {
+ tail->need_adjustment = 0;
+ if (tail->insertion_type)
+ {
+ tail->bytepos = from_byte;
+ tail->charpos = from;
+ }
+ else
+ {
+ tail->bytepos = from_byte + coding->produced;
+ tail->charpos
+ = (NILP (BVAR (current_buffer,
enable_multibyte_characters))
+ ? tail->bytepos : from + coding->produced_char);
+ }
+ }
+ }
+ END_DO_MARKERS;
}
}
@@ -8338,16 +8338,14 @@ encode_coding_object (struct coding_system *coding,
bool same_buffer = false;
if (BASE_EQ (src_object, dst_object) && BUFFERP (src_object))
{
- struct Lisp_Marker *tail;
-
same_buffer = true;
-
- for (tail = BUF_MARKERS (XBUFFER (src_object)); tail; tail = tail->next)
+ DO_MARKERS (XBUFFER (src_object), tail)
{
tail->need_adjustment
= tail->charpos == (tail->insertion_type ? from : to);
need_marker_adjustment |= tail->need_adjustment;
}
+ END_DO_MARKERS;
}
if (! NILP (CODING_ATTR_PRE_WRITE (attrs)))
@@ -8505,25 +8503,26 @@ encode_coding_object (struct coding_system *coding,
if (need_marker_adjustment)
{
- struct Lisp_Marker *tail;
-
- for (tail = BUF_MARKERS (current_buffer); tail; tail = tail->next)
- if (tail->need_adjustment)
- {
- tail->need_adjustment = 0;
- if (tail->insertion_type)
- {
- tail->bytepos = from_byte;
- tail->charpos = from;
- }
- else
- {
- tail->bytepos = from_byte + coding->produced;
- tail->charpos
- = (NILP (BVAR (current_buffer,
enable_multibyte_characters))
- ? tail->bytepos : from + coding->produced_char);
- }
- }
+ DO_MARKERS (current_buffer, tail)
+ {
+ if (tail->need_adjustment)
+ {
+ tail->need_adjustment = 0;
+ if (tail->insertion_type)
+ {
+ tail->bytepos = from_byte;
+ tail->charpos = from;
+ }
+ else
+ {
+ tail->bytepos = from_byte + coding->produced;
+ tail->charpos
+ = (NILP (BVAR (current_buffer,
enable_multibyte_characters))
+ ? tail->bytepos : from + coding->produced_char);
+ }
+ }
+ }
+ END_DO_MARKERS;
}
}
diff --git a/src/editfns.c b/src/editfns.c
index c4f23ccbe5b..6ef93a35fa5 100644
--- a/src/editfns.c
+++ b/src/editfns.c
@@ -4402,7 +4402,6 @@ transpose_markers (ptrdiff_t start1, ptrdiff_t end1,
ptrdiff_t start2_byte, ptrdiff_t end2_byte)
{
register ptrdiff_t amt1, amt1_byte, amt2, amt2_byte, diff, diff_byte, mpos;
- register struct Lisp_Marker *marker;
/* Update point as if it were a marker. */
if (PT < start1)
@@ -4437,7 +4436,7 @@ transpose_markers (ptrdiff_t start1, ptrdiff_t end1,
amt1_byte = (end2_byte - start2_byte) + (start2_byte - end1_byte);
amt2_byte = (end1_byte - start1_byte) + (start2_byte - end1_byte);
- for (marker = BUF_MARKERS (current_buffer); marker; marker = marker->next)
+ DO_MARKERS (current_buffer, marker)
{
mpos = marker->bytepos;
if (mpos >= start1_byte && mpos < end2_byte)
@@ -4462,6 +4461,7 @@ transpose_markers (ptrdiff_t start1, ptrdiff_t end1,
}
marker->charpos = mpos;
}
+ END_DO_MARKERS;
}
DEFUN ("transpose-regions", Ftranspose_regions, Stranspose_regions, 4, 5,
diff --git a/src/insdel.c b/src/insdel.c
index a10cb7c4898..7bfa8dc52c2 100644
--- a/src/insdel.c
+++ b/src/insdel.c
@@ -250,13 +250,12 @@ void
adjust_markers_for_delete (ptrdiff_t from, ptrdiff_t from_byte,
ptrdiff_t to, ptrdiff_t to_byte)
{
- struct Lisp_Marker *m;
ptrdiff_t charpos;
text_index_invalidate (current_buffer, from_byte);
adjust_suspend_auto_hscroll (from, to);
- for (m = BUF_MARKERS (current_buffer); m; m = m->next)
+ DO_MARKERS (current_buffer, m)
{
charpos = m->charpos;
eassert (charpos <= Z);
@@ -275,6 +274,7 @@ adjust_markers_for_delete (ptrdiff_t from, ptrdiff_t
from_byte,
m->bytepos = from_byte;
}
}
+ END_DO_MARKERS;
adjust_overlays_for_delete (from, to - from);
}
@@ -293,12 +293,11 @@ adjust_markers_for_insert (ptrdiff_t from, ptrdiff_t
from_byte,
{
text_index_invalidate (current_buffer, from_byte);
- struct Lisp_Marker *m;
ptrdiff_t nchars = to - from;
ptrdiff_t nbytes = to_byte - from_byte;
adjust_suspend_auto_hscroll (from, to);
- for (m = BUF_MARKERS (current_buffer); m; m = m->next)
+ DO_MARKERS (current_buffer, m)
{
eassert (m->bytepos >= m->charpos
&& m->bytepos - m->charpos <= Z_BYTE - Z);
@@ -317,6 +316,7 @@ adjust_markers_for_insert (ptrdiff_t from, ptrdiff_t
from_byte,
m->charpos += nchars;
}
}
+ END_DO_MARKERS;
adjust_overlays_for_insert (from, to - from, before_markers);
}
@@ -350,7 +350,6 @@ adjust_markers_for_replace (ptrdiff_t from, ptrdiff_t
from_byte,
{
text_index_invalidate (current_buffer, from_byte);
- register struct Lisp_Marker *m;
ptrdiff_t prev_to_byte = from_byte + old_bytes;
ptrdiff_t diff_chars = new_chars - old_chars;
ptrdiff_t diff_bytes = new_bytes - old_bytes;
@@ -369,7 +368,7 @@ adjust_markers_for_replace (ptrdiff_t from, ptrdiff_t
from_byte,
adjust_suspend_auto_hscroll (from, from + old_chars);
- for (m = BUF_MARKERS (current_buffer); m; m = m->next)
+ DO_MARKERS (current_buffer, m)
{
if (m->bytepos >= prev_to_byte)
{
@@ -382,6 +381,7 @@ adjust_markers_for_replace (ptrdiff_t from, ptrdiff_t
from_byte,
m->bytepos = from_byte;
}
}
+ END_DO_MARKERS;
check_markers ();
@@ -420,7 +420,6 @@ void
adjust_markers_bytepos (ptrdiff_t from, ptrdiff_t from_byte,
ptrdiff_t to, ptrdiff_t to_byte, int to_z)
{
- register struct Lisp_Marker *m;
ptrdiff_t beg = from, begbyte = from_byte;
adjust_suspend_auto_hscroll (from, to);
@@ -429,16 +428,17 @@ adjust_markers_bytepos (ptrdiff_t from, ptrdiff_t
from_byte,
{
/* Make sure each affected marker's bytepos is equal to
its charpos. */
- for (m = BUF_MARKERS (current_buffer); m; m = m->next)
+ DO_MARKERS (current_buffer, m)
{
if (m->bytepos > from_byte
&& (to_z || m->bytepos <= to_byte))
m->bytepos = m->charpos;
}
+ END_DO_MARKERS;
}
else
{
- for (m = BUF_MARKERS (current_buffer); m; m = m->next)
+ DO_MARKERS (current_buffer, m)
{
/* Recompute each affected marker's bytepos. */
if (m->bytepos > from_byte
@@ -455,6 +455,7 @@ adjust_markers_bytepos (ptrdiff_t from, ptrdiff_t from_byte,
begbyte = m->bytepos;
}
}
+ END_DO_MARKERS;
}
}
diff --git a/src/lisp.h b/src/lisp.h
index 99d4d79f354..c8ac8a877a0 100644
--- a/src/lisp.h
+++ b/src/lisp.h
@@ -1757,11 +1757,17 @@ ASIZE (Lisp_Object array)
return size;
}
+INLINE ptrdiff_t
+gc_vsize (const struct Lisp_Vector *v)
+{
+ return v->header.size & ~ARRAY_MARK_FLAG;
+}
+
INLINE ptrdiff_t
gc_asize (Lisp_Object array)
{
/* Like ASIZE, but also can be used in the garbage collector. */
- return XVECTOR (array)->header.size & ~ARRAY_MARK_FLAG;
+ return gc_vsize (XVECTOR (array));
}
INLINE ptrdiff_t
@@ -2839,13 +2845,6 @@ struct Lisp_Marker
/* The remaining fields are meaningless in a marker that
does not point anywhere. */
- /* For markers that point somewhere,
- this is used to chain of all the markers in a given buffer.
- The chain does not preserve markers from garbage collection;
- instead, markers are removed from the chain when freed by GC. */
- /* We could remove it and use an array in buffer_text instead.
- That would also allow us to preserve it ordered. */
- struct Lisp_Marker *next;
/* This is the char position where the marker points. */
ptrdiff_t charpos;
/* This is the byte position.
@@ -2853,6 +2852,9 @@ struct Lisp_Marker
used to implement the functionality of markers, but rather to (ab)use
markers as a cache for char<->byte mappings). */
ptrdiff_t bytepos;
+
+ /* If in a buffer's marker vector, this is the entry where it is stored. */
+ ptrdiff_t entry;
} GCALIGNED_STRUCT;
struct Lisp_Overlay
diff --git a/src/marker-vector.c b/src/marker-vector.c
new file mode 100644
index 00000000000..0583d44b98c
--- /dev/null
+++ b/src/marker-vector.c
@@ -0,0 +1,293 @@
+/* Marker vectors..
+ Copyright (C) 2025 Free Software Foundation, Inc.
+
+This file is part of GNU Emacs.
+
+GNU Emacs is free software: you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation, either version 3 of the License, or (at
+your option) any later version.
+
+GNU Emacs is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GNU Emacs. If not, see <https://www.gnu.org/licenses/>. */
+
+/* A marker vector is used to hold the markers of a buffer. The vector
+ is a normal Lisp vector that consists of a header and a number of
+ entries for each marker. A Lisp vector is used because the vector
+ references markers "weakly", and that's what easy for igc.
+
+ +------+-----------+---------+---------+--------------+
+ | FREE | MAX_ENTRY | entry 0 | entry 1 | ... |
+ +------+-----------+---------+---------+--------------+
+ |<----- header --->|
+
+ Entries consist of 2 vector slots MARKER and CHARPOS. MARKER holds a
+ marker, if the entry is in use. CHARPOS is not yet used. (The idea is
+ to move the positions from Lisp_Marker here, which speeds up
+ adjusting positions when the text changes.)
+
+ FREE is the array index of the start of the next free entry in the
+ marker vector. Free entries form a singly-linked list using the
+ MARKER field of entries.
+
+ MAX_ENTRY is the largest index ever used to store a marker. This is
+ used to (supposedly) speed up iteration over the marker vector, with
+ the assumption that there might be a tail of slots in the marker
+ vector that is never used. Or, IOW, that we over-allocate room in the
+ marker vector.
+
+ Lisp_Marker objects contain the index under which they are stored in
+ the marker vector.
+
+ The use of a free list gives O(1) for adding a marker. The index
+ stored in the Lisp_Marker provides O(1) deletion of a marker from
+ the markers of a buffer.
+
+ Iteration over marker vectors is done by iterating over all slots of
+ the vector that can contain markers, skipping those that don't.
+
+ Iteration over markers is O(N) where N is the size of the marker
+ vector. This could be improved to N being the number of live markers
+ by putting marker entries in a doubly-linked list. The downside is
+ that iteration then might access the marker vector slots in an
+ unpredictable order, while the current method scans the vector
+ sequentially which should be fast. */
+
+#include <config.h>
+#include "lisp.h"
+#include "buffer.h"
+#include "marker-vector.h"
+#ifdef HAVE_MPS
+#include "igc.h"
+#endif
+
+/* Number of entries to allocate initially. */
+#define MARKER_VECTOR_INITIAL_ENTRIES 20
+
+/* Access fields of an entry E of marker vector V as lvalues. */
+#define MARKER(v, e) (v)->contents[(e) + MARKER_VECTOR_OFFSET_MARKER]
+#define CHARPOS(v, e) (v)->contents[(e) + MARKER_VECTOR_OFFSET_CHARPOS]
+
+/* Index of next free entry in the header of a marker vector. This must
+ use the marker field so that putting an entry on the free list
+ implicitly sets the marker slot to a non-marker. See
+ fix_marker_vector in igc.c. */
+#define NEXT_FREE(v, e) MARKER (v, e)
+
+/* Value denoting end of the free list. */
+#define FREE_LIST_END make_fixnum (0)
+#define IS_FREE_LIST_END(x) EQ ((x), FREE_LIST_END)
+
+/* Access header fields of marker vector V as lvalues. */
+#define FREE(v) (v)->contents[MARKER_VECTOR_FREE]
+#define MAX_ENTRY(v) (v)->contents[MARKER_VECTOR_MAX_ENTRY]
+
+/* Check that index ENTRY is a valid entry start index in vector V. */
+
+static void
+check_is_entry (const struct Lisp_Vector *v, ptrdiff_t entry)
+{
+ eassert (entry >= MARKER_VECTOR_HEADER_SIZE);
+ eassert (entry < gc_vsize (v));
+ eassert ((entry - MARKER_VECTOR_HEADER_SIZE) % MARKER_VECTOR_ENTRY_SIZE ==
0);
+}
+
+/* Push entry ENTRY of V to its free-list. This must set MARKER to not
+ be a marker, which is done by using the MARKER field of entry
+ to form the free-list. */
+
+static void
+push_free (struct Lisp_Vector *v, const ptrdiff_t entry)
+{
+ check_is_entry (v, entry);
+ NEXT_FREE (v, entry) = FREE (v);
+ FREE (v) = make_fixnum (entry);
+}
+
+/* Pop the next free entry from the free-list of V and return its entry
+ start index. */
+
+static ptrdiff_t
+pop_free (struct Lisp_Vector *v)
+{
+ const ptrdiff_t free = XFIXNUM (FREE (v));
+ FREE (v) = NEXT_FREE (v, free);
+ check_is_entry (v, free);
+ return free;
+}
+
+/* Add a new entry for marker M to marker vector MV and return its entry
+ start index. */
+
+static ptrdiff_t
+add_entry (Lisp_Object mv, struct Lisp_Marker *m)
+{
+ struct Lisp_Vector *v = XVECTOR (mv);
+ const ptrdiff_t entry = pop_free (v);
+ MARKER (v, entry) = make_lisp_ptr (m, Lisp_Vectorlike);
+ const ptrdiff_t max_entry = XFIXNUM (MAX_ENTRY (v));
+ MAX_ENTRY (v) = make_fixnum (max (entry, max_entry));
+ return entry;
+}
+
+/* Allocate a marker vector of length LEN. */
+
+Lisp_Object
+alloc_marker_vector (ptrdiff_t len)
+{
+#ifdef HAVE_MPS
+ return igc_alloc_marker_vector (len, FREE_LIST_END);
+#else
+ return make_vector (len, FREE_LIST_END);
+#endif
+}
+
+/* Expensive pre- and post-condition checking. V is the marker vector to
+ check. ALLOCATING true means we are called from allocation functions
+ where V may be different from the underlying buffer's marker
+ vector. */
+
+static void
+check_marker_vector (struct Lisp_Vector *v, bool allocating)
+{
+#ifdef ENABLE_CHECKING
+ size_t nfree = 0;
+ for (Lisp_Object e = FREE (v); !IS_FREE_LIST_END (e);
+ e = NEXT_FREE (v, XFIXNUM (e)))
+ ++nfree;
+
+ size_t nused = 0;
+ Lisp_Object mv = make_lisp_ptr (v, Lisp_Vectorlike);
+ DO_MARKERS_OF_VECTOR (mv, m)
+ {
+ eassert (m->entry == e_);
+ eassert (m->buffer != NULL);
+ if (!allocating)
+ {
+ struct Lisp_Vector *mv = XVECTOR (BUF_MARKERS (m->buffer));
+ eassert (mv == v);
+ }
+ ++nused;
+ }
+ END_DO_MARKERS;
+
+ eassert ((nused + nfree) * MARKER_VECTOR_ENTRY_SIZE
+ + MARKER_VECTOR_HEADER_SIZE == gc_vsize (v));
+#endif
+}
+
+/* Add all entries of MV starting with FIRST to the end of marker vector MV
+ to its free list. */
+
+static void
+add_to_free_list (Lisp_Object mv, ptrdiff_t first)
+{
+ struct Lisp_Vector *v = XVECTOR (mv);
+ for (ptrdiff_t e = ASIZE (mv) - MARKER_VECTOR_ENTRY_SIZE;
+ e >= first; e -= MARKER_VECTOR_ENTRY_SIZE)
+ push_free (v, e);
+}
+
+/* Make a new marker vector. */
+
+Lisp_Object
+make_marker_vector (void)
+{
+ const ptrdiff_t len
+ = (MARKER_VECTOR_INITIAL_ENTRIES * MARKER_VECTOR_ENTRY_SIZE
+ + MARKER_VECTOR_HEADER_SIZE);
+ Lisp_Object mv = alloc_marker_vector (len);
+ add_to_free_list (mv, MARKER_VECTOR_HEADER_SIZE);
+ check_marker_vector (XVECTOR (mv), true);
+ return mv;
+}
+
+/* Return a new marker vector that is like OLD_MV but larger. */
+
+static Lisp_Object
+larger_marker_vector (Lisp_Object old_mv)
+{
+ const ptrdiff_t old_size = ASIZE (old_mv);
+ const ptrdiff_t old_entries_size = old_size - MARKER_VECTOR_HEADER_SIZE;
+ const ptrdiff_t new_size = 2 * old_entries_size + MARKER_VECTOR_HEADER_SIZE;
+
+ /* Allocate a new marker vector. */
+ Lisp_Object new_mv = alloc_marker_vector (new_size);
+ struct Lisp_Vector *new_v = XVECTOR (new_mv);
+
+ /* Copy existing entries. */
+ const struct Lisp_Vector *old_v = XVECTOR (old_mv);
+ const size_t nbytes = old_size * sizeof (Lisp_Object);
+ memcpy (new_v->contents, old_v->contents, nbytes);
+
+ /* Add new entries to free-list. */
+ add_to_free_list (new_mv, old_size);
+ check_marker_vector (new_v, true);
+ return new_mv;
+}
+
+/* Make sure that the marker vector of buffer B has room for a new
+ entry. Make a larger marker vector if not. Value is the marker
+ vector of B at the end. */
+
+static Lisp_Object
+ensure_room (struct buffer *b)
+{
+ Lisp_Object mv = BUF_MARKERS (b);
+ if (IS_FREE_LIST_END (FREE (XVECTOR (mv))))
+ {
+ mv = larger_marker_vector (mv);
+ BUF_MARKERS (b) = mv;
+ }
+ return mv;
+}
+
+/* Add marker M to the marker vector of buffer B. */
+
+void
+marker_vector_add (struct buffer *b, struct Lisp_Marker *m)
+{
+ const Lisp_Object mv = ensure_room (b);
+ check_marker_vector (XVECTOR (mv), false);
+ m->buffer = b;
+ m->entry = add_entry (mv, m);
+ check_marker_vector (XVECTOR (mv), false);
+}
+
+/* Remove marker M from marker vector V. */
+
+void
+marker_vector_remove (struct Lisp_Vector *v, struct Lisp_Marker *m)
+{
+ check_marker_vector (v, false);
+ check_is_entry (v, m->entry);
+ eassert (MARKERP (MARKER (v, m->entry)));
+ eassert (XMARKER (MARKER (v, m->entry)) == m);
+ push_free (v, m->entry);
+ /* The old GC contains at least one assertion that unchaining markers
+ in kill-buffer resets the markers' buffers. IGC does not do this,
+ can't do this, and does not need it. */
+ m->buffer = NULL;
+ check_marker_vector (v, false);
+}
+
+/* Reset markers of buffer B. Called from kill-buffer. */
+
+void
+marker_vector_reset (struct buffer *b)
+{
+ /* The old GC contains at least one assertion that unchaining markers
+ in kill-buffer resets the markers' buffers. IGC does not do this,
+ can't do this, and does not need it. */
+ DO_MARKERS (b, m)
+ {
+ m->buffer = NULL;
+ }
+ END_DO_MARKERS;
+ BUF_MARKERS (b) = Qnil;
+}
diff --git a/src/marker-vector.h b/src/marker-vector.h
new file mode 100644
index 00000000000..c6abcb0e294
--- /dev/null
+++ b/src/marker-vector.h
@@ -0,0 +1,70 @@
+/* Marker vectors.
+ Copyright (C) 2025 Free Software Foundation, Inc.
+
+This file is part of GNU Emacs.
+
+GNU Emacs is free software: you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation, either version 3 of the License, or (at
+your option) any later version.
+
+GNU Emacs is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GNU Emacs. If not, see <https://www.gnu.org/licenses/>. */
+
+#ifndef EMACS_MARKER_VECTOR_H
+#define EMACS_MARKER_VECTOR_H
+
+#include <config.h>
+#include "lisp.h"
+
+/* A marker vector is a Lisp vector starting with a header of
+ MARKER_VECTOR_HEADER_SIZE Lisp_Objects, followed by entries of
+ MARKER_VECTOR_ENTRY_SIZE Lisp_Objects. */
+
+enum
+{
+ /* Header. */
+ MARKER_VECTOR_FREE = 0,
+ MARKER_VECTOR_MAX_ENTRY = 1,
+ MARKER_VECTOR_HEADER_SIZE = 2,
+
+ /* Entries. */
+ MARKER_VECTOR_OFFSET_MARKER = 0,
+ MARKER_VECTOR_OFFSET_CHARPOS = 1,
+ MARKER_VECTOR_ENTRY_SIZE = 2,
+};
+
+/* Iterate over markers in marker vector MV, binding a variable with
+ name M to a pointer to Lisp_Marker. The loop must be ended
+ with an END_DO_MARKERS. */
+
+# define DO_MARKERS_OF_VECTOR(mv, m) \
+ for (ptrdiff_t e_ = MARKER_VECTOR_HEADER_SIZE, \
+ end_ = XFIXNUM (AREF (mv, MARKER_VECTOR_MAX_ENTRY)); \
+ e_ <= end_; \
+ e_ += MARKER_VECTOR_ENTRY_SIZE) \
+ { \
+ Lisp_Object m_ = AREF (mv, e_ + MARKER_VECTOR_OFFSET_MARKER); \
+ if (MARKERP (m_)) \
+ { \
+ struct Lisp_Marker *m = XMARKER (m_);
+
+/* Iterate over markers of buffer B, binding a variable with name M to a
+ pointer to Lisp_Marker. The loop must be ended with an
+ END_DO_MARKERS. */
+
+# define DO_MARKERS(b, m) DO_MARKERS_OF_VECTOR (BUF_MARKERS (b), m)
+# define END_DO_MARKERS }}
+
+Lisp_Object make_marker_vector (void);
+Lisp_Object alloc_marker_vector (ptrdiff_t len);
+void marker_vector_add (struct buffer *b, struct Lisp_Marker *m);
+void marker_vector_remove (struct Lisp_Vector *v, struct Lisp_Marker *m);
+void marker_vector_reset (struct buffer *b);
+
+#endif /* EMACS_MARKER_VECTOR_H */
diff --git a/src/marker.c b/src/marker.c
index 22929638e51..a528bd315fc 100644
--- a/src/marker.c
+++ b/src/marker.c
@@ -141,9 +141,7 @@ attach_marker (struct Lisp_Marker *m, struct buffer *b,
if (m->buffer != b)
{
unchain_marker (m);
- m->buffer = b;
- m->next = BUF_MARKERS (b);
- BUF_MARKERS (b) = m;
+ marker_vector_add (b, m);
}
}
@@ -336,40 +334,12 @@ detach_marker (Lisp_Object marker)
buffer NULL. */
void
-unchain_marker (register struct Lisp_Marker *marker)
+unchain_marker (struct Lisp_Marker *marker)
{
- register struct buffer *b = marker->buffer;
-
- if (b)
+ if (marker->buffer)
{
- register struct Lisp_Marker *tail, **prev;
-
- /* No dead buffers here. */
- eassert (BUFFER_LIVE_P (b));
-
- marker->buffer = NULL;
- prev = &BUF_MARKERS (b);
-
- for (tail = BUF_MARKERS (b); tail; prev = &tail->next, tail = *prev)
- if (marker == tail)
- {
- if (*prev == BUF_MARKERS (b))
- {
- /* Deleting first marker from the buffer's chain. Crash
- if new first marker in chain does not say it belongs
- to the same buffer, or at least that they have the same
- base buffer. */
- if (tail->next && b->text != tail->next->buffer->text)
- emacs_abort ();
- }
- *prev = tail->next;
- /* We have removed the marker from the chain;
- no need to scan the rest of the chain. */
- break;
- }
-
- /* Error if marker was not in it's chain. */
- eassert (tail != NULL);
+ Lisp_Object mv = BUF_MARKERS (marker->buffer);
+ marker_vector_remove (XVECTOR (mv), marker);
}
}
diff --git a/src/pdumper.c b/src/pdumper.c
index c8255ecab83..3fd25a80b3f 100644
--- a/src/pdumper.c
+++ b/src/pdumper.c
@@ -2129,8 +2129,7 @@ dump_marker (struct dump_context *ctx, const struct
Lisp_Marker *marker)
{
dump_field_lv_rawptr (ctx, out, marker, &marker->buffer,
Lisp_Vectorlike, WEIGHT_NORMAL);
- dump_field_lv_rawptr (ctx, out, marker, &marker->next,
- Lisp_Vectorlike, WEIGHT_STRONG);
+ DUMP_FIELD_COPY (out, marker, entry);
DUMP_FIELD_COPY (out, marker, charpos);
DUMP_FIELD_COPY (out, marker, bytepos);
}
@@ -2874,8 +2873,8 @@ dump_buffer (struct dump_context *ctx, const struct
buffer *in_buffer)
DUMP_FIELD_COPY (out, buffer, own_text.overlay_unchanged_modified);
if (buffer->own_text.intervals)
dump_field_fixup_later (ctx, out, buffer, &buffer->own_text.intervals);
- dump_field_lv_rawptr (ctx, out, buffer, &buffer->own_text.markers,
- Lisp_Vectorlike, WEIGHT_NORMAL);
+ dump_field_lv (ctx, out, buffer, &buffer->own_text.markers,
+ WEIGHT_NORMAL);
DUMP_FIELD_COPY (out, buffer, own_text.inhibit_shrinking);
DUMP_FIELD_COPY (out, buffer, own_text.redisplay);
}
diff --git a/src/undo.c b/src/undo.c
index 87d3fc2602d..21389bdfe36 100644
--- a/src/undo.c
+++ b/src/undo.c
@@ -128,7 +128,7 @@ record_marker_adjustments (ptrdiff_t from, ptrdiff_t to)
{
prepare_record ();
- for (struct Lisp_Marker *m = BUF_MARKERS (current_buffer); m; m = m->next)
+ DO_MARKERS (current_buffer, m)
{
ptrdiff_t charpos = m->charpos;
eassert (charpos <= Z);
@@ -154,6 +154,7 @@ record_marker_adjustments (ptrdiff_t from, ptrdiff_t to)
}
}
}
+ END_DO_MARKERS;
}
/* Record that a deletion is about to take place, of the characters in
- branch scratch/text-index created (now a57c107ab56), Stefan Monnier, 2025/04/23
- scratch/text-index f6b3071a503 5/8: text-index.c: Avoid binary search in charpos->bytepos conversion, Stefan Monnier, 2025/04/23
- scratch/text-index 0b780f86191 6/8: textconv.c: Adjust calls to `build_marker`, Stefan Monnier, 2025/04/23
- scratch/text-index b45ae4c0217 1/8: text-index.c: New implementation of bytepos<->charpos conversion, Stefan Monnier, 2025/04/23
- scratch/text-index a57c107ab56 8/8: (marker_vector_adjust_for_delete): Delete function, Stefan Monnier, 2025/04/23
- scratch/text-index 89ad510b2eb 3/8: marker-vector.c: Move marker's position info to the array, Stefan Monnier, 2025/04/23
- scratch/text-index 109bd2ac2ba 4/8: ; src/marker-vector: Fix typos and punctuation, Stefan Monnier, 2025/04/23
- scratch/text-index c8beb5f0236 7/8: text-index.c: Skip the byte scan when it's all ASCII, Stefan Monnier, 2025/04/23
- scratch/text-index d0a9025fc6f 2/8: marker.c: Keep markers in arrays rather than linked lists,
Stefan Monnier <=