scratch/igc/weak-undo-list a9e3686778e: Replace the marker_to_id table with an id field in markers

branch: scratch/igc/weak-undo-list
commit a9e3686778e8959aec4800e23522f42a38633b6a
Author: Helmut Eller <[email protected]>
Commit: Helmut Eller <[email protected]>

    Replace the marker_to_id table with an id field in markers
    
    This avoids a weak hash table at the cost of adding a field to each
    marker -- even for markers that are never added to the undo list.
    
    * src/lisp.h (struct Lisp_Marker): New field undo_id.
    * src/alloc.c (Fmake_marker, build_marker): Initialize undo_id.
    * src/undo.c (struct weak_marker_table): Remove the marker_to_id field.
    (alloc_weak_marker_id): Set the new undo_id field.
    (syms_of_undo): Remove code for marker_to_id.
---
 src/alloc.c |  5 ++++-
 src/lisp.h  |  3 +++
 src/undo.c  | 46 ++++++++++++++++++++++------------------------
 3 files changed, 29 insertions(+), 25 deletions(-)

diff --git a/src/alloc.c b/src/alloc.c
index e812f4abf1c..b04d468ad2a 100644
--- a/src/alloc.c
+++ b/src/alloc.c
@@ -3974,7 +3974,9 @@ DEFUN ("make-marker", Fmake_marker, Smake_marker, 0, 0, 0,
   p->buffer = 0;
   p->bytepos = 0;
   p->charpos = 0;
-#ifndef HAVE_MPS
+#ifdef HAVE_MPS
+  p->undo_id = -1;
+#else
   p->next = NULL;
 #endif
   p->insertion_type = 0;
@@ -4002,6 +4004,7 @@ build_marker (struct buffer *buf, ptrdiff_t charpos, ptrdiff_t bytepos)
   m->insertion_type = 0;
   m->need_adjustment = 0;
 #ifdef HAVE_MPS
+  m->undo_id = -1;
   igc_add_marker (buf, m);
 #else
   m->next = BUF_MARKERS (buf);
diff --git a/src/lisp.h b/src/lisp.h
index 5aab36fa844..492390ec914 100644
--- a/src/lisp.h
+++ b/src/lisp.h
@@ -3191,6 +3191,9 @@ struct Lisp_Marker
   /* If in a buffer's marker vector, this is the index where it is
      stored. */
   ptrdiff_t slot;
+  /* This is the id for this marker in the undo-list.  Initially it is
+     -1 and only assigned when the marker is added to the undo-list.  */
+  EMACS_INT undo_id;
 # endif
 } GCALIGNED_STRUCT;
 
diff --git a/src/undo.c b/src/undo.c
index 59dba6870c6..a1af187567e 100644
--- a/src/undo.c
+++ b/src/undo.c
@@ -128,10 +128,6 @@ record_insert (ptrdiff_t beg, ptrdiff_t length)
    weak hash table (the id_to_marker field).  Only the id is stored in
    the undo-list.
 
-   The marker_to_id field is another weak hash table that contains the
-   same pairs but in reverse order (marker, id).  We use that to reuse
-   the id of markers that already have an id.
-
    The next_id field is a counter used to generate ids.
 
    The last_count field helps to detect removed markers.  We record
@@ -142,7 +138,6 @@ record_insert (ptrdiff_t beg, ptrdiff_t length)
 struct weak_marker_table
 {
   Lisp_Object id_to_marker;
-  Lisp_Object marker_to_id;
   EMACS_INT next_id;
   EMACS_INT last_count;
 };
@@ -150,7 +145,7 @@ struct weak_marker_table
 static struct weak_marker_table weak_marker_table;
 
 static Lisp_Object
-scrub_id_object_pairs (Lisp_Object id_to_marker, Lisp_Object list)
+scrub_id_offset_pairs (Lisp_Object id_to_marker, Lisp_Object list)
 {
   Lisp_Object tail = list, *prev = &list;
   while (CONSP (tail))
@@ -176,9 +171,10 @@ scrub_id_object_pairs (Lisp_Object id_to_marker, Lisp_Object list)
     }
   return list;
 }
-/* Remove (apply undo--adjust-weak-marker HASHTABLE KEY D) entries
-   where KEY is no longer in HASHTABLE.  */
 
+/* In (apply 0 BEG END undo--adjust-weak-markers . ARGS) entries, remove
+   weak references to markers that are no longer in weak_marker_table.
+   If no weak references remain, remove the entire entry.  */
 static Lisp_Object
 scrub_undo_list (Lisp_Object list)
 {
@@ -195,8 +191,8 @@ scrub_undo_list (Lisp_Object list)
 	{
 	  Lisp_Object htab = weak_marker_table.id_to_marker;
 	  Lisp_Object head = Fnthcdr (make_fixnum (4), entry);
-	  Lisp_Object pairs =
-	    scrub_id_object_pairs (htab, XCDR (head));
+	  Lisp_Object pairs
+	    = scrub_id_offset_pairs (htab, XCDR (head));
 	  XSETCDR (head, pairs);
 	  drop = NILP (pairs);
 	}
@@ -238,19 +234,24 @@ alloc_weak_marker_id (struct weak_marker_table *t, Lisp_Object marker)
   if (count < t->last_count)
     scrub_undo_lists ();
 
-  Lisp_Object id = Fgethash (marker, t->marker_to_id, Qnil);
-  if (!NILP (id) && EQ (Fgethash (id, t->id_to_marker, Qnil), marker))
-    return id;
-
-  do
+  EMACS_INT undo_id = XMARKER (marker)->undo_id;
+  Lisp_Object id;
+  if (undo_id != -1)
+    id = make_fixnum (undo_id);
+  else
     {
-      id = make_fixnum (t->next_id);
-      t->next_id = (t->next_id + 1) % MOST_POSITIVE_FIXNUM;
+      do
+	{
+	  id = make_fixnum (t->next_id);
+	  t->next_id = (t->next_id + 1) % MOST_POSITIVE_FIXNUM;
+	}
+      while (!NILP (Fgethash (id, t->id_to_marker, Qnil)));
+      Fputhash (id, marker, t->id_to_marker);
+      XMARKER (marker)->undo_id = XFIXNUM (id);
+      t->last_count = count + 1;
     }
-  while (!NILP (Fgethash (id, t->id_to_marker, Qnil)));
-  Fputhash (id, marker, t->id_to_marker);
-  Fputhash (marker, id, t->marker_to_id);
-  t->last_count = count + 1;
+  eassert (EQ (Fgethash (id, t->id_to_marker, Qnil), marker));
+  eassert (XMARKER (marker)->undo_id == XFIXNUM (id));
   return id;
 }
 
@@ -688,9 +689,6 @@ so it must make sure not to do a lot of consing.  */);
   DEFSYM (Qundo__adjust_weak_markers, "undo--adjust-weak-markers");
   defsubr (&Sundo__lookup_marker);
   staticpro (&weak_marker_table.id_to_marker);
-  staticpro (&weak_marker_table.marker_to_id);
   weak_marker_table.id_to_marker
     = CALLN (Fmake_hash_table, QCweakness, Qvalue);
-  weak_marker_table.marker_to_id
-    = CALLN (Fmake_hash_table, QCweakness, Qkey);
 }