[Emacs-diffs] master 5cbdaa9 2/4: Use ptrdiff_t instead of Lisp_Object for collision

[Paul Eggert]

branch: master
commit 5cbdaa98f975c870c4afa24346630a18b55f27ab
Author: Paul Eggert <address@hidden>
Commit: Paul Eggert <address@hidden>

    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.
---
 src/alloc.c    |   2 +-
 src/fns.c      | 169 +++++++++++++++++++++++++++++++--------------------------
 src/lisp.h     |  28 +++-------
 src/profiler.c |  10 ++--
 4 files changed, 106 insertions(+), 103 deletions(-)

diff --git a/src/alloc.c b/src/alloc.c
index b579e7e..5da4290 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 2a66531..3769c4e 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 6e02526..027fd07 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 edc28fc8..08ef6ee 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.  */