summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/alloc.c2
-rw-r--r--src/fns.c169
-rw-r--r--src/lisp.h28
-rw-r--r--src/profiler.c10
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. */
generated by cgit v1.2.3 (git 2.39.1) at 2025-04-19 04:15:05 +0000