Use ptrdiff_t instead of Lisp_Object for collision

* src/alloc.c (purecopy_hash_table): Assign, don’t purecopy.
* src/fns.c (set_hash_next_slot, set_hash_index_slot): Hash index
arg is now ptrdiff_t index (or -1 if empty), not Lisp_Object
integer (or Qnil if empty).  All callers changed.
(larger_vecalloc): New static function.
(larger_vector): Use it.
(HASH_NEXT, HASH_INDEX): Move here from lisp.h.  Return ptrdiff_t
index (or -1) not Lisp_Object integer (or Qnil).  All callers changed.
* src/fns.c (make_hash_table, maybe_resize_hash_table, hash_lookup)
(hash_put, hash_remove_from_table, hash_clear, sweep_weak_table):
* src/profiler.c (evict_lower_half, record_backtrace):
-1, not nil, is now the convention for end of collision list.
* src/fns.c (maybe_resize_hash_table): Avoid double-initialization
of the free list.  Reallocate H->next last, in case other
reallocations exhaust memory.
* src/lisp.h (struct Lisp_Hash_Table): ‘next_free’ is now
ptrdiff_t, not Lisp_Object.  Adjust commentary for ‘next’ and
‘index’, which no longer contain nil.
(HASH_NEXT, HASH_INDEX): Move to src/fns.c.

4 files changed, 106 insertions, 103 deletions

diff --git a/src/alloc.c b/src/alloc.c
index b579e7ed1ae..5da4290701e 100644
--- a/src/alloc.c
+++ b/src/alloc.c
@@ -5459,7 +5459,7 @@ purecopy_hash_table (struct Lisp_Hash_Table *table)
   pure->rehash_size = purecopy (table->rehash_size);
   pure->hash = purecopy (table->hash);
   pure->next = purecopy (table->next);
-  pure->next_free = purecopy (table->next_free);
+  pure->next_free = table->next_free;
   pure->index = purecopy (table->index);
   pure->count = table->count;
   pure->pure = table->pure;
diff --git a/src/fns.c b/src/fns.c
index 2a6653144bc..3769c4efb70 100644
--- a/src/fns.c
+++ b/src/fns.c
@@ -3437,9 +3437,9 @@ set_hash_next (struct Lisp_Hash_Table *h, Lisp_Object next)
   h->next = next;
 }
 static void
-set_hash_next_slot (struct Lisp_Hash_Table *h, ptrdiff_t idx, Lisp_Object val)
+set_hash_next_slot (struct Lisp_Hash_Table *h, ptrdiff_t idx, ptrdiff_t val)
 {
-  gc_aset (h->next, idx, val);
+  gc_aset (h->next, idx, make_number (val));
 }
 static void
 set_hash_hash (struct Lisp_Hash_Table *h, Lisp_Object hash)
@@ -3457,9 +3457,9 @@ set_hash_index (struct Lisp_Hash_Table *h, Lisp_Object index)
   h->index = index;
 }
 static void
-set_hash_index_slot (struct Lisp_Hash_Table *h, ptrdiff_t idx, Lisp_Object val)
+set_hash_index_slot (struct Lisp_Hash_Table *h, ptrdiff_t idx, ptrdiff_t val)
 {
-  gc_aset (h->index, idx, val);
+  gc_aset (h->index, idx, make_number (val));
 }
 
 /* If OBJ is a Lisp hash table, return a pointer to its struct
@@ -3513,11 +3513,11 @@ get_key_arg (Lisp_Object key, ptrdiff_t nargs, Lisp_Object *args, char *used)
 /* Return a Lisp vector which has the same contents as VEC but has
    at least INCR_MIN more entries, where INCR_MIN is positive.
    If NITEMS_MAX is not -1, do not grow the vector to be any larger
-   than NITEMS_MAX.  Entries in the resulting
-   vector that are not copied from VEC are set to nil.  */
+   than NITEMS_MAX.  New entries in the resulting vector are
+   uninitialized.  */
 
-Lisp_Object
-larger_vector (Lisp_Object vec, ptrdiff_t incr_min, ptrdiff_t nitems_max)
+static Lisp_Object
+larger_vecalloc (Lisp_Object vec, ptrdiff_t incr_min, ptrdiff_t nitems_max)
 {
   struct Lisp_Vector *v;
   ptrdiff_t incr, incr_max, old_size, new_size;
@@ -3534,16 +3534,46 @@ larger_vector (Lisp_Object vec, ptrdiff_t incr_min, ptrdiff_t nitems_max)
   new_size = old_size + incr;
   v = allocate_vector (new_size);
   memcpy (v->contents, XVECTOR (vec)->contents, old_size * sizeof *v->contents);
-  memclear (v->contents + old_size, incr * word_size);
   XSETVECTOR (vec, v);
   return vec;
 }
 
+/* Likewise, except set new entries in the resulting vector to nil.  */
+
+Lisp_Object
+larger_vector (Lisp_Object vec, ptrdiff_t incr_min, ptrdiff_t nitems_max)
+{
+  ptrdiff_t old_size = ASIZE (vec);
+  Lisp_Object v = larger_vecalloc (vec, incr_min, nitems_max);
+  ptrdiff_t new_size = ASIZE (v);
+  memclear (XVECTOR (v)->contents + old_size,
+            (new_size - old_size) * word_size);
+  return v;
+}
+
 
 /***********************************************************************
                          Low-level Functions
  ***********************************************************************/
 
+/* Return the index of the next entry in H following the one at IDX,
+   or -1 if none.  */
+
+static ptrdiff_t
+HASH_NEXT (struct Lisp_Hash_Table *h, ptrdiff_t idx)
+{
+  return XINT (AREF (h->next, idx));
+}
+
+/* Return the index of the element in hash table H that is the start
+   of the collision list at index IDX, or -1 if the list is empty.  */
+
+static ptrdiff_t
+HASH_INDEX (struct Lisp_Hash_Table *h, ptrdiff_t idx)
+{
+  return XINT (AREF (h->index, idx));
+}
+
 /* Compare KEY1 which has hash code HASH1 and KEY2 with hash code
    HASH2 in hash table H using `eql'.  Value is true if KEY1 and
    KEY2 are the same.  */
@@ -3715,14 +3745,14 @@ make_hash_table (struct hash_table_test test,
   h->count = 0;
   h->key_and_value = Fmake_vector (make_number (2 * sz), Qnil);
   h->hash = Fmake_vector (size, Qnil);
-  h->next = Fmake_vector (size, Qnil);
-  h->index = Fmake_vector (make_number (index_size), Qnil);
+  h->next = Fmake_vector (size, make_number (-1));
+  h->index = Fmake_vector (make_number (index_size), make_number (-1));
   h->pure = pure;
 
   /* Set up the free list.  */
   for (i = 0; i < sz - 1; ++i)
-    set_hash_next_slot (h, i, make_number (i + 1));
-  h->next_free = make_number (0);
+    set_hash_next_slot (h, i, i + 1);
+  h->next_free = 0;
 
   XSET_HASH_TABLE (table, h);
   eassert (HASH_TABLE_P (table));
@@ -3775,7 +3805,7 @@ copy_hash_table (struct Lisp_Hash_Table *h1)
 static void
 maybe_resize_hash_table (struct Lisp_Hash_Table *h)
 {
-  if (NILP (h->next_free))
+  if (h->next_free < 0)
     {
       ptrdiff_t old_size = HASH_TABLE_SIZE (h);
       EMACS_INT new_size, index_size, nsize;
@@ -3813,29 +3843,32 @@ maybe_resize_hash_table (struct Lisp_Hash_Table *h)
 
       set_hash_key_and_value (h, larger_vector (h->key_and_value,
                                                 2 * (new_size - old_size), -1));
-      set_hash_next (h, larger_vector (h->next, new_size - old_size, -1));
       set_hash_hash (h, larger_vector (h->hash, new_size - old_size, -1));
-      set_hash_index (h, Fmake_vector (make_number (index_size), Qnil));
+      set_hash_index (h, Fmake_vector (make_number (index_size),
+                                       make_number (-1)));
+      set_hash_next (h, larger_vecalloc (h->next, new_size - old_size, -1));
 
       /* Update the free list.  Do it so that new entries are added at
          the end of the free list.  This makes some operations like
          maphash faster.  */
       for (i = old_size; i < new_size - 1; ++i)
-        set_hash_next_slot (h, i, make_number (i + 1));
+        set_hash_next_slot (h, i, i + 1);
+      set_hash_next_slot (h, i, -1);
 
-      if (!NILP (h->next_free))
+      if (h->next_free < 0)
+        h->next_free = old_size;
+      else
         {
-          Lisp_Object last, next;
-
-          last = h->next_free;
-          while (next = HASH_NEXT (h, XFASTINT (last)),
-                 !NILP (next))
-            last = next;
-
-          set_hash_next_slot (h, XFASTINT (last), make_number (old_size));
+          ptrdiff_t last = h->next_free;
+          while (true)
+            {
+              ptrdiff_t next = HASH_NEXT (h, last);
+              if (next < 0)
+                break;
+              last = next;
+            }
+          set_hash_next_slot (h, last, old_size);
         }
-      else
-        XSETFASTINT (h->next_free, old_size);
 
       /* Rehash.  */
       for (i = 0; i < old_size; ++i)
@@ -3844,7 +3877,7 @@ maybe_resize_hash_table (struct Lisp_Hash_Table *h)
             EMACS_UINT hash_code = XUINT (HASH_HASH (h, i));
             ptrdiff_t start_of_bucket = hash_code % ASIZE (h->index);
             set_hash_next_slot (h, i, HASH_INDEX (h, start_of_bucket));
-            set_hash_index_slot (h, start_of_bucket, make_number (i));
+            set_hash_index_slot (h, start_of_bucket, i);
           }
     }
 }
@@ -3858,8 +3891,7 @@ ptrdiff_t
 hash_lookup (struct Lisp_Hash_Table *h, Lisp_Object key, EMACS_UINT *hash)
 {
   EMACS_UINT hash_code;
-  ptrdiff_t start_of_bucket;
-  Lisp_Object idx;
+  ptrdiff_t start_of_bucket, i;
 
   hash_code = h->test.hashfn (&h->test, key);
   eassert ((hash_code & ~INTMASK) == 0);
@@ -3867,20 +3899,15 @@ hash_lookup (struct Lisp_Hash_Table *h, Lisp_Object key, EMACS_UINT *hash)
     *hash = hash_code;
 
   start_of_bucket = hash_code % ASIZE (h->index);
-  idx = HASH_INDEX (h, start_of_bucket);
 
-  while (!NILP (idx))
-    {
-      ptrdiff_t i = XFASTINT (idx);
-      if (EQ (key, HASH_KEY (h, i))
-          || (h->test.cmpfn
-              && hash_code == XUINT (HASH_HASH (h, i))
-              && h->test.cmpfn (&h->test, key, HASH_KEY (h, i))))
-        break;
-      idx = HASH_NEXT (h, i);
-    }
+  for (i = HASH_INDEX (h, start_of_bucket); 0 <= i; i = HASH_NEXT (h, i))
+    if (EQ (key, HASH_KEY (h, i))
+        || (h->test.cmpfn
+            && hash_code == XUINT (HASH_HASH (h, i))
+            && h->test.cmpfn (&h->test, key, HASH_KEY (h, i))))
+      break;
 
-  return NILP (idx) ? -1 : XFASTINT (idx);
+  return i;
 }
 
 
@@ -3901,7 +3928,7 @@ hash_put (struct Lisp_Hash_Table *h, Lisp_Object key, Lisp_Object value,
   h->count++;
 
   /* Store key/value in the key_and_value vector.  */
-  i = XFASTINT (h->next_free);
+  i = h->next_free;
   h->next_free = HASH_NEXT (h, i);
   set_hash_key_slot (h, i, key);
   set_hash_value_slot (h, i, value);
@@ -3912,7 +3939,7 @@ hash_put (struct Lisp_Hash_Table *h, Lisp_Object key, Lisp_Object value,
   /* Add new entry to its collision chain.  */
   start_of_bucket = hash % ASIZE (h->index);
   set_hash_next_slot (h, i, HASH_INDEX (h, start_of_bucket));
-  set_hash_index_slot (h, start_of_bucket, make_number (i));
+  set_hash_index_slot (h, start_of_bucket, i);
   return i;
 }
 
@@ -3922,30 +3949,25 @@ hash_put (struct Lisp_Hash_Table *h, Lisp_Object key, Lisp_Object value,
 void
 hash_remove_from_table (struct Lisp_Hash_Table *h, Lisp_Object key)
 {
-  EMACS_UINT hash_code;
-  ptrdiff_t start_of_bucket;
-  Lisp_Object idx, prev;
-
-  hash_code = h->test.hashfn (&h->test, key);
+  EMACS_UINT hash_code = h->test.hashfn (&h->test, key);
   eassert ((hash_code & ~INTMASK) == 0);
-  start_of_bucket = hash_code % ASIZE (h->index);
-  idx = HASH_INDEX (h, start_of_bucket);
-  prev = Qnil;
+  ptrdiff_t start_of_bucket = hash_code % ASIZE (h->index);
+  ptrdiff_t prev = -1;
 
-  while (!NILP (idx))
+  for (ptrdiff_t i = HASH_INDEX (h, start_of_bucket);
+       0 <= i;
+       i = HASH_NEXT (h, i))
     {
-      ptrdiff_t i = XFASTINT (idx);
-
       if (EQ (key, HASH_KEY (h, i))
           || (h->test.cmpfn
               && hash_code == XUINT (HASH_HASH (h, i))
               && h->test.cmpfn (&h->test, key, HASH_KEY (h, i))))
         {
           /* Take entry out of collision chain.  */
-          if (NILP (prev))
+          if (prev < 0)
             set_hash_index_slot (h, start_of_bucket, HASH_NEXT (h, i));
           else
-            set_hash_next_slot (h, XFASTINT (prev), HASH_NEXT (h, i));
+            set_hash_next_slot (h, prev, HASH_NEXT (h, i));
 
           /* Clear slots in key_and_value and add the slots to
              the free list.  */
@@ -3953,16 +3975,13 @@ hash_remove_from_table (struct Lisp_Hash_Table *h, Lisp_Object key)
           set_hash_value_slot (h, i, Qnil);
           set_hash_hash_slot (h, i, Qnil);
           set_hash_next_slot (h, i, h->next_free);
-          h->next_free = make_number (i);
+          h->next_free = i;
           h->count--;
           eassert (h->count >= 0);
           break;
         }
-      else
-        {
-          prev = idx;
-          idx = HASH_NEXT (h, i);
-        }
+
+      prev = i;
     }
 }
 
@@ -3978,16 +3997,16 @@ hash_clear (struct Lisp_Hash_Table *h)
 
       for (i = 0; i < size; ++i)
         {
-          set_hash_next_slot (h, i, i < size - 1 ? make_number (i + 1) : Qnil);
+          set_hash_next_slot (h, i, i < size - 1 ? i + 1 : -1);
           set_hash_key_slot (h, i, Qnil);
           set_hash_value_slot (h, i, Qnil);
           set_hash_hash_slot (h, i, Qnil);
         }
 
       for (i = 0; i < ASIZE (h->index); ++i)
-        ASET (h->index, i, Qnil);
+        ASET (h->index, i, make_number (-1));
 
-      h->next_free = make_number (0);
+      h->next_free = 0;
       h->count = 0;
     }
 }
@@ -4011,14 +4030,12 @@ sweep_weak_table (struct Lisp_Hash_Table *h, bool remove_entries_p)
 
   for (ptrdiff_t bucket = 0; bucket < n; ++bucket)
     {
-      Lisp_Object idx, next, prev;
-
       /* Follow collision chain, removing entries that
          don't survive this garbage collection.  */
-      prev = Qnil;
-      for (idx = HASH_INDEX (h, bucket); !NILP (idx); idx = next)
+      ptrdiff_t prev = -1;
+      ptrdiff_t next;
+      for (ptrdiff_t i = HASH_INDEX (h, bucket); 0 <= i; i = next)
         {
-          ptrdiff_t i = XFASTINT (idx);
           bool key_known_to_survive_p = survives_gc_p (HASH_KEY (h, i));
           bool value_known_to_survive_p = survives_gc_p (HASH_VALUE (h, i));
           bool remove_p;
@@ -4041,14 +4058,14 @@ sweep_weak_table (struct Lisp_Hash_Table *h, bool remove_entries_p)
               if (remove_p)
                 {
                   /* Take out of collision chain.  */
-                  if (NILP (prev))
+                  if (prev < 0)
                     set_hash_index_slot (h, bucket, next);
                   else
-                    set_hash_next_slot (h, XFASTINT (prev), next);
+                    set_hash_next_slot (h, prev, next);
 
                   /* Add to free list.  */
                   set_hash_next_slot (h, i, h->next_free);
-                  h->next_free = idx;
+                  h->next_free = i;
 
                   /* Clear key, value, and hash.  */
                   set_hash_key_slot (h, i, Qnil);
@@ -4059,7 +4076,7 @@ sweep_weak_table (struct Lisp_Hash_Table *h, bool remove_entries_p)
                 }
               else
                 {
-                  prev = idx;
+                  prev = i;
                 }
             }
           else
diff --git a/src/lisp.h b/src/lisp.h
index 6e0252621a6..027fd07d720 100644
--- a/src/lisp.h
+++ b/src/lisp.h
@@ -1980,13 +1980,12 @@ struct Lisp_Hash_Table
 
   /* Vector used to chain entries.  If entry I is free, next[I] is the
      entry number of the next free item.  If entry I is non-free,
-     next[I] is the index of the next entry in the collision chain.  */
+     next[I] is the index of the next entry in the collision chain,
+     or -1 if there is such entry.  */
   Lisp_Object next;
 
-  /* Index of first free entry in free list.  */
-  Lisp_Object next_free;
-
-  /* Bucket vector.  A non-nil entry is the index of the first item in
+  /* Bucket vector.  An entry of -1 indicates no item is present,
+     and a nonnegative entry is the index of the first item in
      a collision chain.  This vector's size can be larger than the
      hash table size to reduce collisions.  */
   Lisp_Object index;
@@ -1998,6 +1997,9 @@ struct Lisp_Hash_Table
   /* Number of key/value entries in the table.  */
   ptrdiff_t count;
 
+  /* Index of first free entry in free list, or -1 if none.  */
+  ptrdiff_t next_free;
+
   /* True if the table can be purecopied.  The table cannot be
      changed afterwards.  */
   bool pure;
@@ -2050,14 +2052,6 @@ HASH_VALUE (struct Lisp_Hash_Table *h, ptrdiff_t idx)
   return AREF (h->key_and_value, 2 * idx + 1);
 }
 
-/* Value is the index of the next entry following the one at IDX
-   in hash table H.  */
-INLINE Lisp_Object
-HASH_NEXT (struct Lisp_Hash_Table *h, ptrdiff_t idx)
-{
-  return AREF (h->next, idx);
-}
-
 /* Value is the hash code computed for entry IDX in hash table H.  */
 INLINE Lisp_Object
 HASH_HASH (struct Lisp_Hash_Table *h, ptrdiff_t idx)
@@ -2065,14 +2059,6 @@ HASH_HASH (struct Lisp_Hash_Table *h, ptrdiff_t idx)
   return AREF (h->hash, idx);
 }
 
-/* Value is the index of the element in hash table H that is the
-   start of the collision list at index IDX in the index vector of H.  */
-INLINE Lisp_Object
-HASH_INDEX (struct Lisp_Hash_Table *h, ptrdiff_t idx)
-{
-  return AREF (h->index, idx);
-}
-
 /* Value is the size of hash table H.  */
 INLINE ptrdiff_t
 HASH_TABLE_SIZE (struct Lisp_Hash_Table *h)
diff --git a/src/profiler.c b/src/profiler.c
index edc28fc8427..08ef6ee9623 100644
--- a/src/profiler.c
+++ b/src/profiler.c
@@ -119,7 +119,7 @@ static void evict_lower_half (log_t *log)
           XSET_HASH_TABLE (tmp, log); /* FIXME: Use make_lisp_ptr.  */
           Fremhash (key, tmp);
         }
-        eassert (EQ (log->next_free, make_number (i)));
+        eassert (log->next_free == i);
 
         eassert (VECTORP (key));
         for (ptrdiff_t j = 0; j < ASIZE (key); j++)
@@ -139,11 +139,11 @@ record_backtrace (log_t *log, EMACS_INT count)
   Lisp_Object backtrace;
   ptrdiff_t index;
 
-  if (!INTEGERP (log->next_free))
+  if (log->next_free < 0)
     /* FIXME: transfer the evicted counts to a special entry rather
        than dropping them on the floor.  */
     evict_lower_half (log);
-  index = XINT (log->next_free);
+  index = log->next_free;
 
   /* Get a "working memory" vector.  */
   backtrace = HASH_KEY (log, index);
@@ -163,8 +163,8 @@ record_backtrace (log_t *log, EMACS_INT count)
       }
     else
       { /* BEWARE!  hash_put in general can allocate memory.
-           But currently it only does that if log->next_free is nil.  */
-        eassert (!NILP (log->next_free));
+           But currently it only does that if log->next_free is -1.  */
+        eassert (0 <= log->next_free);
         ptrdiff_t j = hash_put (log, backtrace, make_number (count), hash);
         /* Let's make sure we've put `backtrace' right where it
            already was to start with.  */