aboutsummaryrefslogtreecommitdiffstats
path: root/src/fns.c
diff options
context:
space:
mode:
authorPaul Eggert2011-05-30 23:05:00 -0700
committerPaul Eggert2011-05-30 23:05:00 -0700
commit0de4bb688da4961269edab53dc0e0d5a30c01a44 (patch)
tree10e3c4d22f03496bf5b8fc4a41ee04cfcc52e33d /src/fns.c
parentb9627cfb1d5b5b0914525a19cd9edb06f91a1665 (diff)
downloademacs-0de4bb688da4961269edab53dc0e0d5a30c01a44.tar.gz
emacs-0de4bb688da4961269edab53dc0e0d5a30c01a44.zip
Remove arbitrary limit of 2**31 entries in hash tables.
* category.c (hash_get_category_set): Use 'EMACS_UINT' and 'EMACS_INT' for hashes and hash indexes, instead of 'unsigned' and 'int'. * ccl.c (ccl_driver): Likewise. * charset.c (Fdefine_charset_internal): Likewise. * charset.h (struct charset.hash_index): Likewise. * composite.c (get_composition_id, gstring_lookup_cache): (composition_gstring_put_cache): Likewise. * composite.h (struct composition.hash_index): Likewise. * dispextern.h (struct image.hash): Likewise. * fns.c (next_almost_prime, larger_vector, cmpfn_eql): (cmpfn_equal, cmpfn_user_defined, hashfn_eq, hashfn_eql): (hashfn_equal, hashfn_user_defined, make_hash_table): (maybe_resize_hash_table, hash_lookup, hash_put): (hash_remove_from_table, hash_clear, sweep_weak_table, SXHASH_COMBINE): (sxhash_string, sxhash_list, sxhash_vector, sxhash_bool_vector): (Fsxhash, Fgethash, Fputhash, Fmaphash): Likewise. * image.c (make_image, search_image_cache, lookup_image): (xpm_put_color_table_h): Likewise. * lisp.h (struct Lisp_Hash_Table): Likewise, for 'count', 'cmpfn', and 'hashfn' members. * minibuf.c (Ftry_completion, Fall_completions, Ftest_completion): Likewise. * print.c (print): Likewise. * alloc.c (allocate_vectorlike): Check for overflow in vector size calculations. * ccl.c (ccl_driver): Check for overflow when converting EMACS_INT to int. * fns.c, image.c: Remove unnecessary static decls that would otherwise need to be updated by these changes. * fns.c (make_hash_table, maybe_resize_hash_table): Check for integer overflow with large hash tables. (make_hash_table, maybe_resize_hash_table, Fmake_hash_table): Prefer the faster XFLOAT_DATA to XFLOATINT where either will do. (SXHASH_REDUCE): New macro. (sxhash_string, sxhash_list, sxhash_vector, sxhash_bool_vector): Use it instead of discarding useful hash info with large hash values. (sxhash_float): New function. (sxhash): Use it. No more need for "& INTMASK" due to above changes. * lisp.h (FIXNUM_BITS): New macro, useful for SXHASH_REDUCE etc. (MOST_NEGATIVE_FIXNUM, MOST_POSITIVE_FIXNUM, INTMASK): Rewrite to use FIXNUM_BITS, as this simplifies things. (next_almost_prime, larger_vector, sxhash, hash_lookup, hash_put): Adjust signatures to match updated version of code. (consing_since_gc): Now EMACS_INT, since a single hash table can use more than INT_MAX bytes.
Diffstat (limited to 'src/fns.c')
-rw-r--r--src/fns.c234
1 files changed, 129 insertions, 105 deletions
diff --git a/src/fns.c b/src/fns.c
index 089f088b63d..4e22276a628 100644
--- a/src/fns.c
+++ b/src/fns.c
@@ -3358,21 +3358,6 @@ static Lisp_Object Qhash_table_test, Qkey_or_value, Qkey_and_value;
3358static struct Lisp_Hash_Table *check_hash_table (Lisp_Object); 3358static struct Lisp_Hash_Table *check_hash_table (Lisp_Object);
3359static size_t get_key_arg (Lisp_Object, size_t, Lisp_Object *, char *); 3359static size_t get_key_arg (Lisp_Object, size_t, Lisp_Object *, char *);
3360static void maybe_resize_hash_table (struct Lisp_Hash_Table *); 3360static void maybe_resize_hash_table (struct Lisp_Hash_Table *);
3361static int cmpfn_eql (struct Lisp_Hash_Table *, Lisp_Object, unsigned,
3362 Lisp_Object, unsigned);
3363static int cmpfn_equal (struct Lisp_Hash_Table *, Lisp_Object, unsigned,
3364 Lisp_Object, unsigned);
3365static int cmpfn_user_defined (struct Lisp_Hash_Table *, Lisp_Object,
3366 unsigned, Lisp_Object, unsigned);
3367static unsigned hashfn_eq (struct Lisp_Hash_Table *, Lisp_Object);
3368static unsigned hashfn_eql (struct Lisp_Hash_Table *, Lisp_Object);
3369static unsigned hashfn_equal (struct Lisp_Hash_Table *, Lisp_Object);
3370static unsigned hashfn_user_defined (struct Lisp_Hash_Table *,
3371 Lisp_Object);
3372static unsigned sxhash_string (unsigned char *, int);
3373static unsigned sxhash_list (Lisp_Object, int);
3374static unsigned sxhash_vector (Lisp_Object, int);
3375static unsigned sxhash_bool_vector (Lisp_Object);
3376static int sweep_weak_table (struct Lisp_Hash_Table *, int); 3361static int sweep_weak_table (struct Lisp_Hash_Table *, int);
3377 3362
3378 3363
@@ -3395,8 +3380,8 @@ check_hash_table (Lisp_Object obj)
3395/* Value is the next integer I >= N, N >= 0 which is "almost" a prime 3380/* Value is the next integer I >= N, N >= 0 which is "almost" a prime
3396 number. */ 3381 number. */
3397 3382
3398int 3383EMACS_INT
3399next_almost_prime (int n) 3384next_almost_prime (EMACS_INT n)
3400{ 3385{
3401 if (n % 2 == 0) 3386 if (n % 2 == 0)
3402 n += 1; 3387 n += 1;
@@ -3436,10 +3421,10 @@ get_key_arg (Lisp_Object key, size_t nargs, Lisp_Object *args, char *used)
3436 vector that are not copied from VEC are set to INIT. */ 3421 vector that are not copied from VEC are set to INIT. */
3437 3422
3438Lisp_Object 3423Lisp_Object
3439larger_vector (Lisp_Object vec, int new_size, Lisp_Object init) 3424larger_vector (Lisp_Object vec, EMACS_INT new_size, Lisp_Object init)
3440{ 3425{
3441 struct Lisp_Vector *v; 3426 struct Lisp_Vector *v;
3442 int i, old_size; 3427 EMACS_INT i, old_size;
3443 3428
3444 xassert (VECTORP (vec)); 3429 xassert (VECTORP (vec));
3445 old_size = ASIZE (vec); 3430 old_size = ASIZE (vec);
@@ -3463,7 +3448,9 @@ larger_vector (Lisp_Object vec, int new_size, Lisp_Object init)
3463 KEY2 are the same. */ 3448 KEY2 are the same. */
3464 3449
3465static int 3450static int
3466cmpfn_eql (struct Lisp_Hash_Table *h, Lisp_Object key1, unsigned int hash1, Lisp_Object key2, unsigned int hash2) 3451cmpfn_eql (struct Lisp_Hash_Table *h,
3452 Lisp_Object key1, EMACS_UINT hash1,
3453 Lisp_Object key2, EMACS_UINT hash2)
3467{ 3454{
3468 return (FLOATP (key1) 3455 return (FLOATP (key1)
3469 && FLOATP (key2) 3456 && FLOATP (key2)
@@ -3476,7 +3463,9 @@ cmpfn_eql (struct Lisp_Hash_Table *h, Lisp_Object key1, unsigned int hash1, Lisp
3476 KEY2 are the same. */ 3463 KEY2 are the same. */
3477 3464
3478static int 3465static int
3479cmpfn_equal (struct Lisp_Hash_Table *h, Lisp_Object key1, unsigned int hash1, Lisp_Object key2, unsigned int hash2) 3466cmpfn_equal (struct Lisp_Hash_Table *h,
3467 Lisp_Object key1, EMACS_UINT hash1,
3468 Lisp_Object key2, EMACS_UINT hash2)
3480{ 3469{
3481 return hash1 == hash2 && !NILP (Fequal (key1, key2)); 3470 return hash1 == hash2 && !NILP (Fequal (key1, key2));
3482} 3471}
@@ -3487,7 +3476,9 @@ cmpfn_equal (struct Lisp_Hash_Table *h, Lisp_Object key1, unsigned int hash1, Li
3487 if KEY1 and KEY2 are the same. */ 3476 if KEY1 and KEY2 are the same. */
3488 3477
3489static int 3478static int
3490cmpfn_user_defined (struct Lisp_Hash_Table *h, Lisp_Object key1, unsigned int hash1, Lisp_Object key2, unsigned int hash2) 3479cmpfn_user_defined (struct Lisp_Hash_Table *h,
3480 Lisp_Object key1, EMACS_UINT hash1,
3481 Lisp_Object key2, EMACS_UINT hash2)
3491{ 3482{
3492 if (hash1 == hash2) 3483 if (hash1 == hash2)
3493 { 3484 {
@@ -3507,10 +3498,10 @@ cmpfn_user_defined (struct Lisp_Hash_Table *h, Lisp_Object key1, unsigned int ha
3507 `eq' to compare keys. The hash code returned is guaranteed to fit 3498 `eq' to compare keys. The hash code returned is guaranteed to fit
3508 in a Lisp integer. */ 3499 in a Lisp integer. */
3509 3500
3510static unsigned 3501static EMACS_UINT
3511hashfn_eq (struct Lisp_Hash_Table *h, Lisp_Object key) 3502hashfn_eq (struct Lisp_Hash_Table *h, Lisp_Object key)
3512{ 3503{
3513 unsigned hash = XUINT (key) ^ XTYPE (key); 3504 EMACS_UINT hash = XUINT (key) ^ XTYPE (key);
3514 xassert ((hash & ~INTMASK) == 0); 3505 xassert ((hash & ~INTMASK) == 0);
3515 return hash; 3506 return hash;
3516} 3507}
@@ -3520,10 +3511,10 @@ hashfn_eq (struct Lisp_Hash_Table *h, Lisp_Object key)
3520 `eql' to compare keys. The hash code returned is guaranteed to fit 3511 `eql' to compare keys. The hash code returned is guaranteed to fit
3521 in a Lisp integer. */ 3512 in a Lisp integer. */
3522 3513
3523static unsigned 3514static EMACS_UINT
3524hashfn_eql (struct Lisp_Hash_Table *h, Lisp_Object key) 3515hashfn_eql (struct Lisp_Hash_Table *h, Lisp_Object key)
3525{ 3516{
3526 unsigned hash; 3517 EMACS_UINT hash;
3527 if (FLOATP (key)) 3518 if (FLOATP (key))
3528 hash = sxhash (key, 0); 3519 hash = sxhash (key, 0);
3529 else 3520 else
@@ -3537,10 +3528,10 @@ hashfn_eql (struct Lisp_Hash_Table *h, Lisp_Object key)
3537 `equal' to compare keys. The hash code returned is guaranteed to fit 3528 `equal' to compare keys. The hash code returned is guaranteed to fit
3538 in a Lisp integer. */ 3529 in a Lisp integer. */
3539 3530
3540static unsigned 3531static EMACS_UINT
3541hashfn_equal (struct Lisp_Hash_Table *h, Lisp_Object key) 3532hashfn_equal (struct Lisp_Hash_Table *h, Lisp_Object key)
3542{ 3533{
3543 unsigned hash = sxhash (key, 0); 3534 EMACS_UINT hash = sxhash (key, 0);
3544 xassert ((hash & ~INTMASK) == 0); 3535 xassert ((hash & ~INTMASK) == 0);
3545 return hash; 3536 return hash;
3546} 3537}
@@ -3550,7 +3541,7 @@ hashfn_equal (struct Lisp_Hash_Table *h, Lisp_Object key)
3550 user-defined function to compare keys. The hash code returned is 3541 user-defined function to compare keys. The hash code returned is
3551 guaranteed to fit in a Lisp integer. */ 3542 guaranteed to fit in a Lisp integer. */
3552 3543
3553static unsigned 3544static EMACS_UINT
3554hashfn_user_defined (struct Lisp_Hash_Table *h, Lisp_Object key) 3545hashfn_user_defined (struct Lisp_Hash_Table *h, Lisp_Object key)
3555{ 3546{
3556 Lisp_Object args[2], hash; 3547 Lisp_Object args[2], hash;
@@ -3593,26 +3584,33 @@ make_hash_table (Lisp_Object test, Lisp_Object size, Lisp_Object rehash_size,
3593{ 3584{
3594 struct Lisp_Hash_Table *h; 3585 struct Lisp_Hash_Table *h;
3595 Lisp_Object table; 3586 Lisp_Object table;
3596 int index_size, i, sz; 3587 EMACS_INT index_size, i, sz;
3588 double index_float;
3597 3589
3598 /* Preconditions. */ 3590 /* Preconditions. */
3599 xassert (SYMBOLP (test)); 3591 xassert (SYMBOLP (test));
3600 xassert (INTEGERP (size) && XINT (size) >= 0); 3592 xassert (INTEGERP (size) && XINT (size) >= 0);
3601 xassert ((INTEGERP (rehash_size) && XINT (rehash_size) > 0) 3593 xassert ((INTEGERP (rehash_size) && XINT (rehash_size) > 0)
3602 || (FLOATP (rehash_size) && XFLOATINT (rehash_size) > 1.0)); 3594 || (FLOATP (rehash_size) && 1 < XFLOAT_DATA (rehash_size)));
3603 xassert (FLOATP (rehash_threshold) 3595 xassert (FLOATP (rehash_threshold)
3604 && XFLOATINT (rehash_threshold) > 0 3596 && 0 < XFLOAT_DATA (rehash_threshold)
3605 && XFLOATINT (rehash_threshold) <= 1.0); 3597 && XFLOAT_DATA (rehash_threshold) <= 1.0);
3606 3598
3607 if (XFASTINT (size) == 0) 3599 if (XFASTINT (size) == 0)
3608 size = make_number (1); 3600 size = make_number (1);
3609 3601
3602 sz = XFASTINT (size);
3603 index_float = sz / XFLOAT_DATA (rehash_threshold);
3604 index_size = (index_float < MOST_POSITIVE_FIXNUM + 1
3605 ? next_almost_prime (index_float)
3606 : MOST_POSITIVE_FIXNUM + 1);
3607 if (MOST_POSITIVE_FIXNUM < max (index_size, 2 * sz))
3608 error ("Hash table too large");
3609
3610 /* Allocate a table and initialize it. */ 3610 /* Allocate a table and initialize it. */
3611 h = allocate_hash_table (); 3611 h = allocate_hash_table ();
3612 3612
3613 /* Initialize hash table slots. */ 3613 /* Initialize hash table slots. */
3614 sz = XFASTINT (size);
3615
3616 h->test = test; 3614 h->test = test;
3617 if (EQ (test, Qeql)) 3615 if (EQ (test, Qeql))
3618 { 3616 {
@@ -3644,8 +3642,6 @@ make_hash_table (Lisp_Object test, Lisp_Object size, Lisp_Object rehash_size,
3644 h->key_and_value = Fmake_vector (make_number (2 * sz), Qnil); 3642 h->key_and_value = Fmake_vector (make_number (2 * sz), Qnil);
3645 h->hash = Fmake_vector (size, Qnil); 3643 h->hash = Fmake_vector (size, Qnil);
3646 h->next = Fmake_vector (size, Qnil); 3644 h->next = Fmake_vector (size, Qnil);
3647 /* Cast to int here avoids losing with gcc 2.95 on Tru64/Alpha... */
3648 index_size = next_almost_prime ((int) (sz / XFLOATINT (rehash_threshold)));
3649 h->index = Fmake_vector (make_number (index_size), Qnil); 3645 h->index = Fmake_vector (make_number (index_size), Qnil);
3650 3646
3651 /* Set up the free list. */ 3647 /* Set up the free list. */
@@ -3709,20 +3705,29 @@ maybe_resize_hash_table (struct Lisp_Hash_Table *h)
3709{ 3705{
3710 if (NILP (h->next_free)) 3706 if (NILP (h->next_free))
3711 { 3707 {
3712 int old_size = HASH_TABLE_SIZE (h); 3708 EMACS_INT old_size = HASH_TABLE_SIZE (h);
3713 int i, new_size, index_size; 3709 EMACS_INT i, new_size, index_size;
3714 EMACS_INT nsize; 3710 EMACS_INT nsize;
3711 double index_float;
3715 3712
3716 if (INTEGERP (h->rehash_size)) 3713 if (INTEGERP (h->rehash_size))
3717 new_size = old_size + XFASTINT (h->rehash_size); 3714 new_size = old_size + XFASTINT (h->rehash_size);
3718 else 3715 else
3719 new_size = old_size * XFLOATINT (h->rehash_size); 3716 {
3720 new_size = max (old_size + 1, new_size); 3717 double float_new_size = old_size * XFLOAT_DATA (h->rehash_size);
3721 index_size = next_almost_prime ((int) 3718 if (float_new_size < MOST_POSITIVE_FIXNUM + 1)
3722 (new_size 3719 {
3723 / XFLOATINT (h->rehash_threshold))); 3720 new_size = float_new_size;
3724 /* Assignment to EMACS_INT stops GCC whining about limited range 3721 if (new_size <= old_size)
3725 of data type. */ 3722 new_size = old_size + 1;
3723 }
3724 else
3725 new_size = MOST_POSITIVE_FIXNUM + 1;
3726 }
3727 index_float = new_size / XFLOAT_DATA (h->rehash_threshold);
3728 index_size = (index_float < MOST_POSITIVE_FIXNUM + 1
3729 ? next_almost_prime (index_float)
3730 : MOST_POSITIVE_FIXNUM + 1);
3726 nsize = max (index_size, 2 * new_size); 3731 nsize = max (index_size, 2 * new_size);
3727 if (nsize > MOST_POSITIVE_FIXNUM) 3732 if (nsize > MOST_POSITIVE_FIXNUM)
3728 error ("Hash table too large to resize"); 3733 error ("Hash table too large to resize");
@@ -3756,8 +3761,8 @@ maybe_resize_hash_table (struct Lisp_Hash_Table *h)
3756 for (i = 0; i < old_size; ++i) 3761 for (i = 0; i < old_size; ++i)
3757 if (!NILP (HASH_HASH (h, i))) 3762 if (!NILP (HASH_HASH (h, i)))
3758 { 3763 {
3759 unsigned hash_code = XUINT (HASH_HASH (h, i)); 3764 EMACS_UINT hash_code = XUINT (HASH_HASH (h, i));
3760 int start_of_bucket = hash_code % ASIZE (h->index); 3765 EMACS_INT start_of_bucket = hash_code % ASIZE (h->index);
3761 HASH_NEXT (h, i) = HASH_INDEX (h, start_of_bucket); 3766 HASH_NEXT (h, i) = HASH_INDEX (h, start_of_bucket);
3762 HASH_INDEX (h, start_of_bucket) = make_number (i); 3767 HASH_INDEX (h, start_of_bucket) = make_number (i);
3763 } 3768 }
@@ -3769,11 +3774,11 @@ maybe_resize_hash_table (struct Lisp_Hash_Table *h)
3769 the hash code of KEY. Value is the index of the entry in H 3774 the hash code of KEY. Value is the index of the entry in H
3770 matching KEY, or -1 if not found. */ 3775 matching KEY, or -1 if not found. */
3771 3776
3772int 3777EMACS_INT
3773hash_lookup (struct Lisp_Hash_Table *h, Lisp_Object key, unsigned int *hash) 3778hash_lookup (struct Lisp_Hash_Table *h, Lisp_Object key, EMACS_UINT *hash)
3774{ 3779{
3775 unsigned hash_code; 3780 EMACS_UINT hash_code;
3776 int start_of_bucket; 3781 EMACS_INT start_of_bucket;
3777 Lisp_Object idx; 3782 Lisp_Object idx;
3778 3783
3779 hash_code = h->hashfn (h, key); 3784 hash_code = h->hashfn (h, key);
@@ -3786,7 +3791,7 @@ hash_lookup (struct Lisp_Hash_Table *h, Lisp_Object key, unsigned int *hash)
3786 /* We need not gcpro idx since it's either an integer or nil. */ 3791 /* We need not gcpro idx since it's either an integer or nil. */
3787 while (!NILP (idx)) 3792 while (!NILP (idx))
3788 { 3793 {
3789 int i = XFASTINT (idx); 3794 EMACS_INT i = XFASTINT (idx);
3790 if (EQ (key, HASH_KEY (h, i)) 3795 if (EQ (key, HASH_KEY (h, i))
3791 || (h->cmpfn 3796 || (h->cmpfn
3792 && h->cmpfn (h, key, hash_code, 3797 && h->cmpfn (h, key, hash_code,
@@ -3803,10 +3808,11 @@ hash_lookup (struct Lisp_Hash_Table *h, Lisp_Object key, unsigned int *hash)
3803 HASH is a previously computed hash code of KEY. 3808 HASH is a previously computed hash code of KEY.
3804 Value is the index of the entry in H matching KEY. */ 3809 Value is the index of the entry in H matching KEY. */
3805 3810
3806int 3811EMACS_INT
3807hash_put (struct Lisp_Hash_Table *h, Lisp_Object key, Lisp_Object value, unsigned int hash) 3812hash_put (struct Lisp_Hash_Table *h, Lisp_Object key, Lisp_Object value,
3813 EMACS_UINT hash)
3808{ 3814{
3809 int start_of_bucket, i; 3815 EMACS_INT start_of_bucket, i;
3810 3816
3811 xassert ((hash & ~INTMASK) == 0); 3817 xassert ((hash & ~INTMASK) == 0);
3812 3818
@@ -3836,8 +3842,8 @@ hash_put (struct Lisp_Hash_Table *h, Lisp_Object key, Lisp_Object value, unsigne
3836static void 3842static void
3837hash_remove_from_table (struct Lisp_Hash_Table *h, Lisp_Object key) 3843hash_remove_from_table (struct Lisp_Hash_Table *h, Lisp_Object key)
3838{ 3844{
3839 unsigned hash_code; 3845 EMACS_UINT hash_code;
3840 int start_of_bucket; 3846 EMACS_INT start_of_bucket;
3841 Lisp_Object idx, prev; 3847 Lisp_Object idx, prev;
3842 3848
3843 hash_code = h->hashfn (h, key); 3849 hash_code = h->hashfn (h, key);
@@ -3848,7 +3854,7 @@ hash_remove_from_table (struct Lisp_Hash_Table *h, Lisp_Object key)
3848 /* We need not gcpro idx, prev since they're either integers or nil. */ 3854 /* We need not gcpro idx, prev since they're either integers or nil. */
3849 while (!NILP (idx)) 3855 while (!NILP (idx))
3850 { 3856 {
3851 int i = XFASTINT (idx); 3857 EMACS_INT i = XFASTINT (idx);
3852 3858
3853 if (EQ (key, HASH_KEY (h, i)) 3859 if (EQ (key, HASH_KEY (h, i))
3854 || (h->cmpfn 3860 || (h->cmpfn
@@ -3886,7 +3892,7 @@ hash_clear (struct Lisp_Hash_Table *h)
3886{ 3892{
3887 if (h->count > 0) 3893 if (h->count > 0)
3888 { 3894 {
3889 int i, size = HASH_TABLE_SIZE (h); 3895 EMACS_INT i, size = HASH_TABLE_SIZE (h);
3890 3896
3891 for (i = 0; i < size; ++i) 3897 for (i = 0; i < size; ++i)
3892 { 3898 {
@@ -3924,7 +3930,8 @@ init_weak_hash_tables (void)
3924static int 3930static int
3925sweep_weak_table (struct Lisp_Hash_Table *h, int remove_entries_p) 3931sweep_weak_table (struct Lisp_Hash_Table *h, int remove_entries_p)
3926{ 3932{
3927 int bucket, n, marked; 3933 EMACS_INT bucket, n;
3934 int marked;
3928 3935
3929 n = ASIZE (h->index) & ~ARRAY_MARK_FLAG; 3936 n = ASIZE (h->index) & ~ARRAY_MARK_FLAG;
3930 marked = 0; 3937 marked = 0;
@@ -3938,7 +3945,7 @@ sweep_weak_table (struct Lisp_Hash_Table *h, int remove_entries_p)
3938 prev = Qnil; 3945 prev = Qnil;
3939 for (idx = HASH_INDEX (h, bucket); !NILP (idx); idx = next) 3946 for (idx = HASH_INDEX (h, bucket); !NILP (idx); idx = next)
3940 { 3947 {
3941 int i = XFASTINT (idx); 3948 EMACS_INT i = XFASTINT (idx);
3942 int key_known_to_survive_p = survives_gc_p (HASH_KEY (h, i)); 3949 int key_known_to_survive_p = survives_gc_p (HASH_KEY (h, i));
3943 int value_known_to_survive_p = survives_gc_p (HASH_VALUE (h, i)); 3950 int value_known_to_survive_p = survives_gc_p (HASH_VALUE (h, i));
3944 int remove_p; 3951 int remove_p;
@@ -4067,43 +4074,68 @@ sweep_weak_hash_tables (void)
4067 4074
4068#define SXHASH_MAX_LEN 7 4075#define SXHASH_MAX_LEN 7
4069 4076
4070/* Combine two integers X and Y for hashing. */ 4077/* Combine two integers X and Y for hashing. The result might not fit
4078 into a Lisp integer. */
4071 4079
4072#define SXHASH_COMBINE(X, Y) \ 4080#define SXHASH_COMBINE(X, Y) \
4073 ((((unsigned)(X) << 4) + (((unsigned)(X) >> 24) & 0x0fffffff)) \ 4081 ((((EMACS_UINT) (X) << 4) + ((EMACS_UINT) (X) >> (BITS_PER_EMACS_INT - 4))) \
4074 + (unsigned)(Y)) 4082 + (EMACS_UINT) (Y))
4075 4083
4084/* Hash X, returning a value that fits into a Lisp integer. */
4085#define SXHASH_REDUCE(X) \
4086 ((((X) ^ (X) >> (BITS_PER_EMACS_INT - FIXNUM_BITS))) & INTMASK)
4076 4087
4077/* Return a hash for string PTR which has length LEN. The hash 4088/* Return a hash for string PTR which has length LEN. The hash
4078 code returned is guaranteed to fit in a Lisp integer. */ 4089 code returned is guaranteed to fit in a Lisp integer. */
4079 4090
4080static unsigned 4091static EMACS_UINT
4081sxhash_string (unsigned char *ptr, int len) 4092sxhash_string (unsigned char *ptr, EMACS_INT len)
4082{ 4093{
4083 unsigned char *p = ptr; 4094 unsigned char *p = ptr;
4084 unsigned char *end = p + len; 4095 unsigned char *end = p + len;
4085 unsigned char c; 4096 unsigned char c;
4086 unsigned hash = 0; 4097 EMACS_UINT hash = 0;
4087 4098
4088 while (p != end) 4099 while (p != end)
4089 { 4100 {
4090 c = *p++; 4101 c = *p++;
4091 if (c >= 0140) 4102 if (c >= 0140)
4092 c -= 40; 4103 c -= 40;
4093 hash = ((hash << 4) + (hash >> 28) + c); 4104 hash = SXHASH_COMBINE (hash, c);
4094 } 4105 }
4095 4106
4096 return hash & INTMASK; 4107 return SXHASH_REDUCE (hash);
4097} 4108}
4098 4109
4110/* Return a hash for the floating point value VAL. */
4111
4112static EMACS_INT
4113sxhash_float (double val)
4114{
4115 EMACS_UINT hash = 0;
4116 enum {
4117 WORDS_PER_DOUBLE = (sizeof val / sizeof hash
4118 + (sizeof val % sizeof hash != 0))
4119 };
4120 union {
4121 double val;
4122 EMACS_UINT word[WORDS_PER_DOUBLE];
4123 } u;
4124 int i;
4125 u.val = val;
4126 memset (&u.val + 1, 0, sizeof u - sizeof u.val);
4127 for (i = 0; i < WORDS_PER_DOUBLE; i++)
4128 hash = SXHASH_COMBINE (hash, u.word[i]);
4129 return SXHASH_REDUCE (hash);
4130}
4099 4131
4100/* Return a hash for list LIST. DEPTH is the current depth in the 4132/* Return a hash for list LIST. DEPTH is the current depth in the
4101 list. We don't recurse deeper than SXHASH_MAX_DEPTH in it. */ 4133 list. We don't recurse deeper than SXHASH_MAX_DEPTH in it. */
4102 4134
4103static unsigned 4135static EMACS_UINT
4104sxhash_list (Lisp_Object list, int depth) 4136sxhash_list (Lisp_Object list, int depth)
4105{ 4137{
4106 unsigned hash = 0; 4138 EMACS_UINT hash = 0;
4107 int i; 4139 int i;
4108 4140
4109 if (depth < SXHASH_MAX_DEPTH) 4141 if (depth < SXHASH_MAX_DEPTH)
@@ -4111,63 +4143,62 @@ sxhash_list (Lisp_Object list, int depth)
4111 CONSP (list) && i < SXHASH_MAX_LEN; 4143 CONSP (list) && i < SXHASH_MAX_LEN;
4112 list = XCDR (list), ++i) 4144 list = XCDR (list), ++i)
4113 { 4145 {
4114 unsigned hash2 = sxhash (XCAR (list), depth + 1); 4146 EMACS_UINT hash2 = sxhash (XCAR (list), depth + 1);
4115 hash = SXHASH_COMBINE (hash, hash2); 4147 hash = SXHASH_COMBINE (hash, hash2);
4116 } 4148 }
4117 4149
4118 if (!NILP (list)) 4150 if (!NILP (list))
4119 { 4151 {
4120 unsigned hash2 = sxhash (list, depth + 1); 4152 EMACS_UINT hash2 = sxhash (list, depth + 1);
4121 hash = SXHASH_COMBINE (hash, hash2); 4153 hash = SXHASH_COMBINE (hash, hash2);
4122 } 4154 }
4123 4155
4124 return hash; 4156 return SXHASH_REDUCE (hash);
4125} 4157}
4126 4158
4127 4159
4128/* Return a hash for vector VECTOR. DEPTH is the current depth in 4160/* Return a hash for vector VECTOR. DEPTH is the current depth in
4129 the Lisp structure. */ 4161 the Lisp structure. */
4130 4162
4131static unsigned 4163static EMACS_UINT
4132sxhash_vector (Lisp_Object vec, int depth) 4164sxhash_vector (Lisp_Object vec, int depth)
4133{ 4165{
4134 unsigned hash = ASIZE (vec); 4166 EMACS_UINT hash = ASIZE (vec);
4135 int i, n; 4167 int i, n;
4136 4168
4137 n = min (SXHASH_MAX_LEN, ASIZE (vec)); 4169 n = min (SXHASH_MAX_LEN, ASIZE (vec));
4138 for (i = 0; i < n; ++i) 4170 for (i = 0; i < n; ++i)
4139 { 4171 {
4140 unsigned hash2 = sxhash (AREF (vec, i), depth + 1); 4172 EMACS_UINT hash2 = sxhash (AREF (vec, i), depth + 1);
4141 hash = SXHASH_COMBINE (hash, hash2); 4173 hash = SXHASH_COMBINE (hash, hash2);
4142 } 4174 }
4143 4175
4144 return hash; 4176 return SXHASH_REDUCE (hash);
4145} 4177}
4146 4178
4147
4148/* Return a hash for bool-vector VECTOR. */ 4179/* Return a hash for bool-vector VECTOR. */
4149 4180
4150static unsigned 4181static EMACS_UINT
4151sxhash_bool_vector (Lisp_Object vec) 4182sxhash_bool_vector (Lisp_Object vec)
4152{ 4183{
4153 unsigned hash = XBOOL_VECTOR (vec)->size; 4184 EMACS_UINT hash = XBOOL_VECTOR (vec)->size;
4154 int i, n; 4185 int i, n;
4155 4186
4156 n = min (SXHASH_MAX_LEN, XBOOL_VECTOR (vec)->header.size); 4187 n = min (SXHASH_MAX_LEN, XBOOL_VECTOR (vec)->header.size);
4157 for (i = 0; i < n; ++i) 4188 for (i = 0; i < n; ++i)
4158 hash = SXHASH_COMBINE (hash, XBOOL_VECTOR (vec)->data[i]); 4189 hash = SXHASH_COMBINE (hash, XBOOL_VECTOR (vec)->data[i]);
4159 4190
4160 return hash; 4191 return SXHASH_REDUCE (hash);
4161} 4192}
4162 4193
4163 4194
4164/* Return a hash code for OBJ. DEPTH is the current depth in the Lisp 4195/* Return a hash code for OBJ. DEPTH is the current depth in the Lisp
4165 structure. Value is an unsigned integer clipped to INTMASK. */ 4196 structure. Value is an unsigned integer clipped to INTMASK. */
4166 4197
4167unsigned 4198EMACS_UINT
4168sxhash (Lisp_Object obj, int depth) 4199sxhash (Lisp_Object obj, int depth)
4169{ 4200{
4170 unsigned hash; 4201 EMACS_UINT hash;
4171 4202
4172 if (depth > SXHASH_MAX_DEPTH) 4203 if (depth > SXHASH_MAX_DEPTH)
4173 return 0; 4204 return 0;
@@ -4211,20 +4242,14 @@ sxhash (Lisp_Object obj, int depth)
4211 break; 4242 break;
4212 4243
4213 case Lisp_Float: 4244 case Lisp_Float:
4214 { 4245 hash = sxhash_float (XFLOAT_DATA (obj));
4215 double val = XFLOAT_DATA (obj); 4246 break;
4216 unsigned char *p = (unsigned char *) &val;
4217 size_t i;
4218 for (hash = 0, i = 0; i < sizeof val; i++)
4219 hash = SXHASH_COMBINE (hash, p[i]);
4220 break;
4221 }
4222 4247
4223 default: 4248 default:
4224 abort (); 4249 abort ();
4225 } 4250 }
4226 4251
4227 return hash & INTMASK; 4252 return hash;
4228} 4253}
4229 4254
4230 4255
@@ -4238,7 +4263,7 @@ DEFUN ("sxhash", Fsxhash, Ssxhash, 1, 1, 0,
4238 doc: /* Compute a hash code for OBJ and return it as integer. */) 4263 doc: /* Compute a hash code for OBJ and return it as integer. */)
4239 (Lisp_Object obj) 4264 (Lisp_Object obj)
4240{ 4265{
4241 unsigned hash = sxhash (obj, 0); 4266 EMACS_UINT hash = sxhash (obj, 0);
4242 return make_number (hash); 4267 return make_number (hash);
4243} 4268}
4244 4269
@@ -4315,17 +4340,16 @@ usage: (make-hash-table &rest KEYWORD-ARGS) */)
4315 /* Look for `:rehash-size SIZE'. */ 4340 /* Look for `:rehash-size SIZE'. */
4316 i = get_key_arg (QCrehash_size, nargs, args, used); 4341 i = get_key_arg (QCrehash_size, nargs, args, used);
4317 rehash_size = i ? args[i] : make_float (DEFAULT_REHASH_SIZE); 4342 rehash_size = i ? args[i] : make_float (DEFAULT_REHASH_SIZE);
4318 if (!NUMBERP (rehash_size) 4343 if (! ((INTEGERP (rehash_size) && 0 < XINT (rehash_size))
4319 || (INTEGERP (rehash_size) && XINT (rehash_size) <= 0) 4344 || (FLOATP (rehash_size) && 1 < XFLOAT_DATA (rehash_size))))
4320 || XFLOATINT (rehash_size) <= 1.0)
4321 signal_error ("Invalid hash table rehash size", rehash_size); 4345 signal_error ("Invalid hash table rehash size", rehash_size);
4322 4346
4323 /* Look for `:rehash-threshold THRESHOLD'. */ 4347 /* Look for `:rehash-threshold THRESHOLD'. */
4324 i = get_key_arg (QCrehash_threshold, nargs, args, used); 4348 i = get_key_arg (QCrehash_threshold, nargs, args, used);
4325 rehash_threshold = i ? args[i] : make_float (DEFAULT_REHASH_THRESHOLD); 4349 rehash_threshold = i ? args[i] : make_float (DEFAULT_REHASH_THRESHOLD);
4326 if (!FLOATP (rehash_threshold) 4350 if (! (FLOATP (rehash_threshold)
4327 || XFLOATINT (rehash_threshold) <= 0.0 4351 && 0 < XFLOAT_DATA (rehash_threshold)
4328 || XFLOATINT (rehash_threshold) > 1.0) 4352 && XFLOAT_DATA (rehash_threshold) <= 1))
4329 signal_error ("Invalid hash table rehash threshold", rehash_threshold); 4353 signal_error ("Invalid hash table rehash threshold", rehash_threshold);
4330 4354
4331 /* Look for `:weakness WEAK'. */ 4355 /* Look for `:weakness WEAK'. */
@@ -4437,7 +4461,7 @@ If KEY is not found, return DFLT which defaults to nil. */)
4437 (Lisp_Object key, Lisp_Object table, Lisp_Object dflt) 4461 (Lisp_Object key, Lisp_Object table, Lisp_Object dflt)
4438{ 4462{
4439 struct Lisp_Hash_Table *h = check_hash_table (table); 4463 struct Lisp_Hash_Table *h = check_hash_table (table);
4440 int i = hash_lookup (h, key, NULL); 4464 EMACS_INT i = hash_lookup (h, key, NULL);
4441 return i >= 0 ? HASH_VALUE (h, i) : dflt; 4465 return i >= 0 ? HASH_VALUE (h, i) : dflt;
4442} 4466}
4443 4467
@@ -4449,8 +4473,8 @@ VALUE. */)
4449 (Lisp_Object key, Lisp_Object value, Lisp_Object table) 4473 (Lisp_Object key, Lisp_Object value, Lisp_Object table)
4450{ 4474{
4451 struct Lisp_Hash_Table *h = check_hash_table (table); 4475 struct Lisp_Hash_Table *h = check_hash_table (table);
4452 int i; 4476 EMACS_INT i;
4453 unsigned hash; 4477 EMACS_UINT hash;
4454 4478
4455 i = hash_lookup (h, key, &hash); 4479 i = hash_lookup (h, key, &hash);
4456 if (i >= 0) 4480 if (i >= 0)
@@ -4479,7 +4503,7 @@ FUNCTION is called with two arguments, KEY and VALUE. */)
4479{ 4503{
4480 struct Lisp_Hash_Table *h = check_hash_table (table); 4504 struct Lisp_Hash_Table *h = check_hash_table (table);
4481 Lisp_Object args[3]; 4505 Lisp_Object args[3];
4482 int i; 4506 EMACS_INT i;
4483 4507
4484 for (i = 0; i < HASH_TABLE_SIZE (h); ++i) 4508 for (i = 0; i < HASH_TABLE_SIZE (h); ++i)
4485 if (!NILP (HASH_HASH (h, i))) 4509 if (!NILP (HASH_HASH (h, i)))