diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/fns.c | 87 |
1 files changed, 29 insertions, 58 deletions
| @@ -3804,36 +3804,16 @@ CHECK_HASH_TABLE (Lisp_Object x) | |||
| 3804 | } | 3804 | } |
| 3805 | 3805 | ||
| 3806 | static void | 3806 | static void |
| 3807 | set_hash_key_and_value (struct Lisp_Hash_Table *h, Lisp_Object key_and_value) | ||
| 3808 | { | ||
| 3809 | h->key_and_value = key_and_value; | ||
| 3810 | } | ||
| 3811 | static void | ||
| 3812 | set_hash_next (struct Lisp_Hash_Table *h, Lisp_Object next) | ||
| 3813 | { | ||
| 3814 | h->next = next; | ||
| 3815 | } | ||
| 3816 | static void | ||
| 3817 | set_hash_next_slot (struct Lisp_Hash_Table *h, ptrdiff_t idx, ptrdiff_t val) | 3807 | set_hash_next_slot (struct Lisp_Hash_Table *h, ptrdiff_t idx, ptrdiff_t val) |
| 3818 | { | 3808 | { |
| 3819 | gc_aset (h->next, idx, make_fixnum (val)); | 3809 | gc_aset (h->next, idx, make_fixnum (val)); |
| 3820 | } | 3810 | } |
| 3821 | static void | 3811 | static void |
| 3822 | set_hash_hash (struct Lisp_Hash_Table *h, Lisp_Object hash) | ||
| 3823 | { | ||
| 3824 | h->hash = hash; | ||
| 3825 | } | ||
| 3826 | static void | ||
| 3827 | set_hash_hash_slot (struct Lisp_Hash_Table *h, ptrdiff_t idx, Lisp_Object val) | 3812 | set_hash_hash_slot (struct Lisp_Hash_Table *h, ptrdiff_t idx, Lisp_Object val) |
| 3828 | { | 3813 | { |
| 3829 | gc_aset (h->hash, idx, val); | 3814 | gc_aset (h->hash, idx, val); |
| 3830 | } | 3815 | } |
| 3831 | static void | 3816 | static void |
| 3832 | set_hash_index (struct Lisp_Hash_Table *h, Lisp_Object index) | ||
| 3833 | { | ||
| 3834 | h->index = index; | ||
| 3835 | } | ||
| 3836 | static void | ||
| 3837 | set_hash_index_slot (struct Lisp_Hash_Table *h, ptrdiff_t idx, ptrdiff_t val) | 3817 | set_hash_index_slot (struct Lisp_Hash_Table *h, ptrdiff_t idx, ptrdiff_t val) |
| 3838 | { | 3818 | { |
| 3839 | gc_aset (h->index, idx, make_fixnum (val)); | 3819 | gc_aset (h->index, idx, make_fixnum (val)); |
| @@ -4159,10 +4139,8 @@ maybe_resize_hash_table (struct Lisp_Hash_Table *h) | |||
| 4159 | if (h->next_free < 0) | 4139 | if (h->next_free < 0) |
| 4160 | { | 4140 | { |
| 4161 | ptrdiff_t old_size = HASH_TABLE_SIZE (h); | 4141 | ptrdiff_t old_size = HASH_TABLE_SIZE (h); |
| 4162 | EMACS_INT new_size, index_size, nsize; | 4142 | EMACS_INT new_size; |
| 4163 | ptrdiff_t i; | ||
| 4164 | double rehash_size = h->rehash_size; | 4143 | double rehash_size = h->rehash_size; |
| 4165 | double index_float; | ||
| 4166 | 4144 | ||
| 4167 | if (rehash_size < 0) | 4145 | if (rehash_size < 0) |
| 4168 | new_size = old_size - rehash_size; | 4146 | new_size = old_size - rehash_size; |
| @@ -4177,50 +4155,38 @@ maybe_resize_hash_table (struct Lisp_Hash_Table *h) | |||
| 4177 | if (new_size <= old_size) | 4155 | if (new_size <= old_size) |
| 4178 | new_size = old_size + 1; | 4156 | new_size = old_size + 1; |
| 4179 | double threshold = h->rehash_threshold; | 4157 | double threshold = h->rehash_threshold; |
| 4180 | index_float = new_size / threshold; | 4158 | double index_float = new_size / threshold; |
| 4181 | index_size = (index_float < INDEX_SIZE_BOUND + 1 | 4159 | EMACS_INT index_size = (index_float < INDEX_SIZE_BOUND + 1 |
| 4182 | ? next_almost_prime (index_float) | 4160 | ? next_almost_prime (index_float) |
| 4183 | : INDEX_SIZE_BOUND + 1); | 4161 | : INDEX_SIZE_BOUND + 1); |
| 4184 | nsize = max (index_size, 2 * new_size); | 4162 | if (INDEX_SIZE_BOUND < max (index_size, 2 * new_size)) |
| 4185 | if (INDEX_SIZE_BOUND < nsize) | ||
| 4186 | error ("Hash table too large to resize"); | 4163 | error ("Hash table too large to resize"); |
| 4187 | 4164 | ||
| 4188 | #ifdef ENABLE_CHECKING | 4165 | /* Allocate all the new vectors before updating *H, to |
| 4189 | if (HASH_TABLE_P (Vpurify_flag) | 4166 | avoid problems if memory is exhausted. larger_vecalloc |
| 4190 | && XHASH_TABLE (Vpurify_flag) == h) | 4167 | finishes computing the size of the replacement vectors. */ |
| 4191 | message ("Growing hash table to: %"pI"d", new_size); | 4168 | Lisp_Object next = larger_vecalloc (h->next, new_size - old_size, -1); |
| 4192 | #endif | 4169 | ptrdiff_t next_size = ASIZE (next); |
| 4193 | 4170 | Lisp_Object key_and_value | |
| 4194 | set_hash_key_and_value (h, larger_vector (h->key_and_value, | 4171 | = larger_vector (h->key_and_value, 2 * (next_size - old_size), |
| 4195 | 2 * (new_size - old_size), -1)); | 4172 | 2 * next_size); |
| 4196 | set_hash_hash (h, larger_vector (h->hash, new_size - old_size, -1)); | 4173 | Lisp_Object hash = larger_vector (h->hash, next_size - old_size, |
| 4197 | set_hash_index (h, make_vector (index_size, make_fixnum (-1))); | 4174 | next_size); |
| 4198 | set_hash_next (h, larger_vecalloc (h->next, new_size - old_size, -1)); | 4175 | h->index = make_vector (index_size, make_fixnum (-1)); |
| 4176 | h->key_and_value = key_and_value; | ||
| 4177 | h->hash = hash; | ||
| 4178 | h->next = next; | ||
| 4199 | 4179 | ||
| 4200 | /* Update the free list. Do it so that new entries are added at | 4180 | /* Update the free list. Do it so that new entries are added at |
| 4201 | the end of the free list. This makes some operations like | 4181 | the end of the free list. This makes some operations like |
| 4202 | maphash faster. */ | 4182 | maphash faster. */ |
| 4203 | for (i = old_size; i < new_size - 1; ++i) | 4183 | for (ptrdiff_t i = old_size; i < next_size - 1; i++) |
| 4204 | set_hash_next_slot (h, i, i + 1); | 4184 | set_hash_next_slot (h, i, i + 1); |
| 4205 | set_hash_next_slot (h, i, -1); | 4185 | set_hash_next_slot (h, next_size - 1, -1); |
| 4206 | 4186 | h->next_free = old_size; | |
| 4207 | if (h->next_free < 0) | ||
| 4208 | h->next_free = old_size; | ||
| 4209 | else | ||
| 4210 | { | ||
| 4211 | ptrdiff_t last = h->next_free; | ||
| 4212 | while (true) | ||
| 4213 | { | ||
| 4214 | ptrdiff_t next = HASH_NEXT (h, last); | ||
| 4215 | if (next < 0) | ||
| 4216 | break; | ||
| 4217 | last = next; | ||
| 4218 | } | ||
| 4219 | set_hash_next_slot (h, last, old_size); | ||
| 4220 | } | ||
| 4221 | 4187 | ||
| 4222 | /* Rehash. */ | 4188 | /* Rehash. */ |
| 4223 | for (i = 0; i < old_size; ++i) | 4189 | for (ptrdiff_t i = 0; i < old_size; i++) |
| 4224 | if (!NILP (HASH_HASH (h, i))) | 4190 | if (!NILP (HASH_HASH (h, i))) |
| 4225 | { | 4191 | { |
| 4226 | EMACS_UINT hash_code = XUFIXNUM (HASH_HASH (h, i)); | 4192 | EMACS_UINT hash_code = XUFIXNUM (HASH_HASH (h, i)); |
| @@ -4228,6 +4194,11 @@ maybe_resize_hash_table (struct Lisp_Hash_Table *h) | |||
| 4228 | set_hash_next_slot (h, i, HASH_INDEX (h, start_of_bucket)); | 4194 | set_hash_next_slot (h, i, HASH_INDEX (h, start_of_bucket)); |
| 4229 | set_hash_index_slot (h, start_of_bucket, i); | 4195 | set_hash_index_slot (h, start_of_bucket, i); |
| 4230 | } | 4196 | } |
| 4197 | |||
| 4198 | #ifdef ENABLE_CHECKING | ||
| 4199 | if (HASH_TABLE_P (Vpurify_flag) && XHASH_TABLE (Vpurify_flag) == h) | ||
| 4200 | message ("Growing hash table to: %"pD"d", new_size); | ||
| 4201 | #endif | ||
| 4231 | } | 4202 | } |
| 4232 | } | 4203 | } |
| 4233 | 4204 | ||