diff options
| -rw-r--r-- | src/ChangeLog | 49 | ||||
| -rw-r--r-- | src/alloc.c | 10 | ||||
| -rw-r--r-- | src/category.c | 4 | ||||
| -rw-r--r-- | src/ccl.c | 16 | ||||
| -rw-r--r-- | src/charset.c | 2 | ||||
| -rw-r--r-- | src/charset.h | 2 | ||||
| -rw-r--r-- | src/composite.c | 8 | ||||
| -rw-r--r-- | src/composite.h | 2 | ||||
| -rw-r--r-- | src/dispextern.h | 2 | ||||
| -rw-r--r-- | src/fns.c | 234 | ||||
| -rw-r--r-- | src/image.c | 10 | ||||
| -rw-r--r-- | src/lisp.h | 47 | ||||
| -rw-r--r-- | src/minibuf.c | 6 | ||||
| -rw-r--r-- | src/print.c | 2 |
14 files changed, 234 insertions, 160 deletions
diff --git a/src/ChangeLog b/src/ChangeLog index fa8022b0d4d..029585b803f 100644 --- a/src/ChangeLog +++ b/src/ChangeLog @@ -1,5 +1,54 @@ 2011-05-31 Paul Eggert <eggert@cs.ucla.edu> + 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. + +2011-05-31 Paul Eggert <eggert@cs.ucla.edu> + Use 'inline', not 'INLINE'. <http://lists.gnu.org/archive/html/emacs-devel/2011-05/msg00914.html> * alloc.c, fontset.c (INLINE): Remove. diff --git a/src/alloc.c b/src/alloc.c index e627af6c071..8fcc6f91df9 100644 --- a/src/alloc.c +++ b/src/alloc.c @@ -157,7 +157,7 @@ struct emacs_globals globals; /* Number of bytes of consing done since the last gc. */ -int consing_since_gc; +EMACS_INT consing_since_gc; /* Similar minimum, computed from Vgc_cons_percentage. */ @@ -2788,6 +2788,11 @@ allocate_vectorlike (EMACS_INT len) { struct Lisp_Vector *p; size_t nbytes; + int header_size = offsetof (struct Lisp_Vector, contents); + int word_size = sizeof p->contents[0]; + + if ((SIZE_MAX - header_size) / word_size < len) + memory_full (); MALLOC_BLOCK_INPUT; @@ -2801,8 +2806,7 @@ allocate_vectorlike (EMACS_INT len) /* This gets triggered by code which I haven't bothered to fix. --Stef */ /* eassert (!handling_signal); */ - nbytes = (offsetof (struct Lisp_Vector, contents) - + len * sizeof p->contents[0]); + nbytes = header_size + len * word_size; p = (struct Lisp_Vector *) lisp_malloc (nbytes, MEM_TYPE_VECTORLIKE); #ifdef DOUG_LEA_MALLOC diff --git a/src/category.c b/src/category.c index 356801a179c..23fd874c824 100644 --- a/src/category.c +++ b/src/category.c @@ -67,8 +67,8 @@ static Lisp_Object hash_get_category_set (Lisp_Object table, Lisp_Object category_set) { struct Lisp_Hash_Table *h; - int i; - unsigned hash; + EMACS_INT i; + EMACS_UINT hash; if (NILP (XCHAR_TABLE (table)->extras[1])) XCHAR_TABLE (table)->extras[1] diff --git a/src/ccl.c b/src/ccl.c index b04c74ccc25..e2ef4f194f3 100644 --- a/src/ccl.c +++ b/src/ccl.c @@ -1307,15 +1307,15 @@ ccl_driver (struct ccl_program *ccl, int *source, int *destination, int src_size : -1)); h = GET_HASH_TABLE (eop); - op = hash_lookup (h, make_number (reg[RRR]), NULL); - if (op >= 0) + eop = hash_lookup (h, make_number (reg[RRR]), NULL); + if (eop >= 0) { Lisp_Object opl; - opl = HASH_VALUE (h, op); - if (! CHARACTERP (opl)) + opl = HASH_VALUE (h, eop); + if (! (IN_INT_RANGE (eop) && CHARACTERP (opl))) CCL_INVALID_CMD; reg[RRR] = charset_unicode; - reg[rrr] = op; + reg[rrr] = eop; reg[7] = 1; /* r7 true for success */ } else @@ -1334,11 +1334,11 @@ ccl_driver (struct ccl_program *ccl, int *source, int *destination, int src_size i = CCL_DECODE_CHAR (reg[RRR], reg[rrr]); h = GET_HASH_TABLE (eop); - op = hash_lookup (h, make_number (i), NULL); - if (op >= 0) + eop = hash_lookup (h, make_number (i), NULL); + if (eop >= 0) { Lisp_Object opl; - opl = HASH_VALUE (h, op); + opl = HASH_VALUE (h, eop); if (! (INTEGERP (opl) && IN_INT_RANGE (XINT (opl)))) CCL_INVALID_CMD; reg[RRR] = XINT (opl); diff --git a/src/charset.c b/src/charset.c index b1b4993d277..0af21b48ad2 100644 --- a/src/charset.c +++ b/src/charset.c @@ -849,7 +849,7 @@ usage: (define-charset-internal ...) */) /* Charset attr vector. */ Lisp_Object attrs; Lisp_Object val; - unsigned hash_code; + EMACS_UINT hash_code; struct Lisp_Hash_Table *hash_table = XHASH_TABLE (Vcharset_hash_table); int i, j; struct charset charset; diff --git a/src/charset.h b/src/charset.h index 53784bf8455..16f45ff9865 100644 --- a/src/charset.h +++ b/src/charset.h @@ -146,7 +146,7 @@ struct charset int id; /* Index to Vcharset_hash_table. */ - int hash_index; + EMACS_INT hash_index; /* Dimension of the charset: 1, 2, 3, or 4. */ int dimension; diff --git a/src/composite.c b/src/composite.c index 7849ffa3a18..ab9ec3f5a03 100644 --- a/src/composite.c +++ b/src/composite.c @@ -179,8 +179,8 @@ get_composition_id (EMACS_INT charpos, EMACS_INT bytepos, EMACS_INT nchars, Lisp_Object id, length, components, key, *key_contents; int glyph_len; struct Lisp_Hash_Table *hash_table = XHASH_TABLE (composition_hash_table); - int hash_index; - unsigned hash_code; + EMACS_INT hash_index; + EMACS_UINT hash_code; struct composition *cmp; EMACS_INT i; int ch; @@ -656,7 +656,7 @@ static Lisp_Object gstring_lookup_cache (Lisp_Object header) { struct Lisp_Hash_Table *h = XHASH_TABLE (gstring_hash_table); - int i = hash_lookup (h, header, NULL); + EMACS_INT i = hash_lookup (h, header, NULL); return (i >= 0 ? HASH_VALUE (h, i) : Qnil); } @@ -665,7 +665,7 @@ Lisp_Object composition_gstring_put_cache (Lisp_Object gstring, EMACS_INT len) { struct Lisp_Hash_Table *h = XHASH_TABLE (gstring_hash_table); - unsigned hash; + EMACS_UINT hash; Lisp_Object header, copy; EMACS_INT i; diff --git a/src/composite.h b/src/composite.h index 5188f981d9c..cc8ca10a139 100644 --- a/src/composite.h +++ b/src/composite.h @@ -186,7 +186,7 @@ struct composition { enum composition_method method; /* Index to the composition hash table. */ - int hash_index; + EMACS_INT hash_index; /* For which font we have calculated the remaining members. The actual type is device dependent. */ diff --git a/src/dispextern.h b/src/dispextern.h index 5d8b4562499..e612a8b1eba 100644 --- a/src/dispextern.h +++ b/src/dispextern.h @@ -2798,7 +2798,7 @@ struct image } data; /* Hash value of image specification to speed up comparisons. */ - unsigned hash; + EMACS_UINT hash; /* Image id of this image. */ int id; 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; static struct Lisp_Hash_Table *check_hash_table (Lisp_Object); static size_t get_key_arg (Lisp_Object, size_t, Lisp_Object *, char *); static void maybe_resize_hash_table (struct Lisp_Hash_Table *); -static int cmpfn_eql (struct Lisp_Hash_Table *, Lisp_Object, unsigned, - Lisp_Object, unsigned); -static int cmpfn_equal (struct Lisp_Hash_Table *, Lisp_Object, unsigned, - Lisp_Object, unsigned); -static int cmpfn_user_defined (struct Lisp_Hash_Table *, Lisp_Object, - unsigned, Lisp_Object, unsigned); -static unsigned hashfn_eq (struct Lisp_Hash_Table *, Lisp_Object); -static unsigned hashfn_eql (struct Lisp_Hash_Table *, Lisp_Object); -static unsigned hashfn_equal (struct Lisp_Hash_Table *, Lisp_Object); -static unsigned hashfn_user_defined (struct Lisp_Hash_Table *, - Lisp_Object); -static unsigned sxhash_string (unsigned char *, int); -static unsigned sxhash_list (Lisp_Object, int); -static unsigned sxhash_vector (Lisp_Object, int); -static unsigned sxhash_bool_vector (Lisp_Object); static int sweep_weak_table (struct Lisp_Hash_Table *, int); @@ -3395,8 +3380,8 @@ check_hash_table (Lisp_Object obj) /* Value is the next integer I >= N, N >= 0 which is "almost" a prime number. */ -int -next_almost_prime (int n) +EMACS_INT +next_almost_prime (EMACS_INT n) { if (n % 2 == 0) n += 1; @@ -3436,10 +3421,10 @@ get_key_arg (Lisp_Object key, size_t nargs, Lisp_Object *args, char *used) vector that are not copied from VEC are set to INIT. */ Lisp_Object -larger_vector (Lisp_Object vec, int new_size, Lisp_Object init) +larger_vector (Lisp_Object vec, EMACS_INT new_size, Lisp_Object init) { struct Lisp_Vector *v; - int i, old_size; + EMACS_INT i, old_size; xassert (VECTORP (vec)); old_size = ASIZE (vec); @@ -3463,7 +3448,9 @@ larger_vector (Lisp_Object vec, int new_size, Lisp_Object init) KEY2 are the same. */ static int -cmpfn_eql (struct Lisp_Hash_Table *h, Lisp_Object key1, unsigned int hash1, Lisp_Object key2, unsigned int hash2) +cmpfn_eql (struct Lisp_Hash_Table *h, + Lisp_Object key1, EMACS_UINT hash1, + Lisp_Object key2, EMACS_UINT hash2) { return (FLOATP (key1) && FLOATP (key2) @@ -3476,7 +3463,9 @@ cmpfn_eql (struct Lisp_Hash_Table *h, Lisp_Object key1, unsigned int hash1, Lisp KEY2 are the same. */ static int -cmpfn_equal (struct Lisp_Hash_Table *h, Lisp_Object key1, unsigned int hash1, Lisp_Object key2, unsigned int hash2) +cmpfn_equal (struct Lisp_Hash_Table *h, + Lisp_Object key1, EMACS_UINT hash1, + Lisp_Object key2, EMACS_UINT hash2) { return hash1 == hash2 && !NILP (Fequal (key1, key2)); } @@ -3487,7 +3476,9 @@ cmpfn_equal (struct Lisp_Hash_Table *h, Lisp_Object key1, unsigned int hash1, Li if KEY1 and KEY2 are the same. */ static int -cmpfn_user_defined (struct Lisp_Hash_Table *h, Lisp_Object key1, unsigned int hash1, Lisp_Object key2, unsigned int hash2) +cmpfn_user_defined (struct Lisp_Hash_Table *h, + Lisp_Object key1, EMACS_UINT hash1, + Lisp_Object key2, EMACS_UINT hash2) { if (hash1 == hash2) { @@ -3507,10 +3498,10 @@ cmpfn_user_defined (struct Lisp_Hash_Table *h, Lisp_Object key1, unsigned int ha `eq' to compare keys. The hash code returned is guaranteed to fit in a Lisp integer. */ -static unsigned +static EMACS_UINT hashfn_eq (struct Lisp_Hash_Table *h, Lisp_Object key) { - unsigned hash = XUINT (key) ^ XTYPE (key); + EMACS_UINT hash = XUINT (key) ^ XTYPE (key); xassert ((hash & ~INTMASK) == 0); return hash; } @@ -3520,10 +3511,10 @@ hashfn_eq (struct Lisp_Hash_Table *h, Lisp_Object key) `eql' to compare keys. The hash code returned is guaranteed to fit in a Lisp integer. */ -static unsigned +static EMACS_UINT hashfn_eql (struct Lisp_Hash_Table *h, Lisp_Object key) { - unsigned hash; + EMACS_UINT hash; if (FLOATP (key)) hash = sxhash (key, 0); else @@ -3537,10 +3528,10 @@ hashfn_eql (struct Lisp_Hash_Table *h, Lisp_Object key) `equal' to compare keys. The hash code returned is guaranteed to fit in a Lisp integer. */ -static unsigned +static EMACS_UINT hashfn_equal (struct Lisp_Hash_Table *h, Lisp_Object key) { - unsigned hash = sxhash (key, 0); + EMACS_UINT hash = sxhash (key, 0); xassert ((hash & ~INTMASK) == 0); return hash; } @@ -3550,7 +3541,7 @@ hashfn_equal (struct Lisp_Hash_Table *h, Lisp_Object key) user-defined function to compare keys. The hash code returned is guaranteed to fit in a Lisp integer. */ -static unsigned +static EMACS_UINT hashfn_user_defined (struct Lisp_Hash_Table *h, Lisp_Object key) { Lisp_Object args[2], hash; @@ -3593,26 +3584,33 @@ make_hash_table (Lisp_Object test, Lisp_Object size, Lisp_Object rehash_size, { struct Lisp_Hash_Table *h; Lisp_Object table; - int index_size, i, sz; + EMACS_INT index_size, i, sz; + double index_float; /* Preconditions. */ xassert (SYMBOLP (test)); xassert (INTEGERP (size) && XINT (size) >= 0); xassert ((INTEGERP (rehash_size) && XINT (rehash_size) > 0) - || (FLOATP (rehash_size) && XFLOATINT (rehash_size) > 1.0)); + || (FLOATP (rehash_size) && 1 < XFLOAT_DATA (rehash_size))); xassert (FLOATP (rehash_threshold) - && XFLOATINT (rehash_threshold) > 0 - && XFLOATINT (rehash_threshold) <= 1.0); + && 0 < XFLOAT_DATA (rehash_threshold) + && XFLOAT_DATA (rehash_threshold) <= 1.0); if (XFASTINT (size) == 0) size = make_number (1); + sz = XFASTINT (size); + index_float = sz / XFLOAT_DATA (rehash_threshold); + index_size = (index_float < MOST_POSITIVE_FIXNUM + 1 + ? next_almost_prime (index_float) + : MOST_POSITIVE_FIXNUM + 1); + if (MOST_POSITIVE_FIXNUM < max (index_size, 2 * sz)) + error ("Hash table too large"); + /* Allocate a table and initialize it. */ h = allocate_hash_table (); /* Initialize hash table slots. */ - sz = XFASTINT (size); - h->test = test; if (EQ (test, Qeql)) { @@ -3644,8 +3642,6 @@ make_hash_table (Lisp_Object test, Lisp_Object size, Lisp_Object rehash_size, h->key_and_value = Fmake_vector (make_number (2 * sz), Qnil); h->hash = Fmake_vector (size, Qnil); h->next = Fmake_vector (size, Qnil); - /* Cast to int here avoids losing with gcc 2.95 on Tru64/Alpha... */ - index_size = next_almost_prime ((int) (sz / XFLOATINT (rehash_threshold))); h->index = Fmake_vector (make_number (index_size), Qnil); /* Set up the free list. */ @@ -3709,20 +3705,29 @@ maybe_resize_hash_table (struct Lisp_Hash_Table *h) { if (NILP (h->next_free)) { - int old_size = HASH_TABLE_SIZE (h); - int i, new_size, index_size; + EMACS_INT old_size = HASH_TABLE_SIZE (h); + EMACS_INT i, new_size, index_size; EMACS_INT nsize; + double index_float; if (INTEGERP (h->rehash_size)) new_size = old_size + XFASTINT (h->rehash_size); else - new_size = old_size * XFLOATINT (h->rehash_size); - new_size = max (old_size + 1, new_size); - index_size = next_almost_prime ((int) - (new_size - / XFLOATINT (h->rehash_threshold))); - /* Assignment to EMACS_INT stops GCC whining about limited range - of data type. */ + { + double float_new_size = old_size * XFLOAT_DATA (h->rehash_size); + if (float_new_size < MOST_POSITIVE_FIXNUM + 1) + { + new_size = float_new_size; + if (new_size <= old_size) + new_size = old_size + 1; + } + else + new_size = MOST_POSITIVE_FIXNUM + 1; + } + index_float = new_size / XFLOAT_DATA (h->rehash_threshold); + index_size = (index_float < MOST_POSITIVE_FIXNUM + 1 + ? next_almost_prime (index_float) + : MOST_POSITIVE_FIXNUM + 1); nsize = max (index_size, 2 * new_size); if (nsize > MOST_POSITIVE_FIXNUM) error ("Hash table too large to resize"); @@ -3756,8 +3761,8 @@ maybe_resize_hash_table (struct Lisp_Hash_Table *h) for (i = 0; i < old_size; ++i) if (!NILP (HASH_HASH (h, i))) { - unsigned hash_code = XUINT (HASH_HASH (h, i)); - int start_of_bucket = hash_code % ASIZE (h->index); + EMACS_UINT hash_code = XUINT (HASH_HASH (h, i)); + EMACS_INT start_of_bucket = hash_code % ASIZE (h->index); HASH_NEXT (h, i) = HASH_INDEX (h, start_of_bucket); HASH_INDEX (h, start_of_bucket) = make_number (i); } @@ -3769,11 +3774,11 @@ maybe_resize_hash_table (struct Lisp_Hash_Table *h) the hash code of KEY. Value is the index of the entry in H matching KEY, or -1 if not found. */ -int -hash_lookup (struct Lisp_Hash_Table *h, Lisp_Object key, unsigned int *hash) +EMACS_INT +hash_lookup (struct Lisp_Hash_Table *h, Lisp_Object key, EMACS_UINT *hash) { - unsigned hash_code; - int start_of_bucket; + EMACS_UINT hash_code; + EMACS_INT start_of_bucket; Lisp_Object idx; hash_code = h->hashfn (h, key); @@ -3786,7 +3791,7 @@ hash_lookup (struct Lisp_Hash_Table *h, Lisp_Object key, unsigned int *hash) /* We need not gcpro idx since it's either an integer or nil. */ while (!NILP (idx)) { - int i = XFASTINT (idx); + EMACS_INT i = XFASTINT (idx); if (EQ (key, HASH_KEY (h, i)) || (h->cmpfn && h->cmpfn (h, key, hash_code, @@ -3803,10 +3808,11 @@ hash_lookup (struct Lisp_Hash_Table *h, Lisp_Object key, unsigned int *hash) HASH is a previously computed hash code of KEY. Value is the index of the entry in H matching KEY. */ -int -hash_put (struct Lisp_Hash_Table *h, Lisp_Object key, Lisp_Object value, unsigned int hash) +EMACS_INT +hash_put (struct Lisp_Hash_Table *h, Lisp_Object key, Lisp_Object value, + EMACS_UINT hash) { - int start_of_bucket, i; + EMACS_INT start_of_bucket, i; xassert ((hash & ~INTMASK) == 0); @@ -3836,8 +3842,8 @@ hash_put (struct Lisp_Hash_Table *h, Lisp_Object key, Lisp_Object value, unsigne static void hash_remove_from_table (struct Lisp_Hash_Table *h, Lisp_Object key) { - unsigned hash_code; - int start_of_bucket; + EMACS_UINT hash_code; + EMACS_INT start_of_bucket; Lisp_Object idx, prev; hash_code = h->hashfn (h, key); @@ -3848,7 +3854,7 @@ hash_remove_from_table (struct Lisp_Hash_Table *h, Lisp_Object key) /* We need not gcpro idx, prev since they're either integers or nil. */ while (!NILP (idx)) { - int i = XFASTINT (idx); + EMACS_INT i = XFASTINT (idx); if (EQ (key, HASH_KEY (h, i)) || (h->cmpfn @@ -3886,7 +3892,7 @@ hash_clear (struct Lisp_Hash_Table *h) { if (h->count > 0) { - int i, size = HASH_TABLE_SIZE (h); + EMACS_INT i, size = HASH_TABLE_SIZE (h); for (i = 0; i < size; ++i) { @@ -3924,7 +3930,8 @@ init_weak_hash_tables (void) static int sweep_weak_table (struct Lisp_Hash_Table *h, int remove_entries_p) { - int bucket, n, marked; + EMACS_INT bucket, n; + int marked; n = ASIZE (h->index) & ~ARRAY_MARK_FLAG; marked = 0; @@ -3938,7 +3945,7 @@ sweep_weak_table (struct Lisp_Hash_Table *h, int remove_entries_p) prev = Qnil; for (idx = HASH_INDEX (h, bucket); !NILP (idx); idx = next) { - int i = XFASTINT (idx); + EMACS_INT i = XFASTINT (idx); int key_known_to_survive_p = survives_gc_p (HASH_KEY (h, i)); int value_known_to_survive_p = survives_gc_p (HASH_VALUE (h, i)); int remove_p; @@ -4067,43 +4074,68 @@ sweep_weak_hash_tables (void) #define SXHASH_MAX_LEN 7 -/* Combine two integers X and Y for hashing. */ +/* Combine two integers X and Y for hashing. The result might not fit + into a Lisp integer. */ #define SXHASH_COMBINE(X, Y) \ - ((((unsigned)(X) << 4) + (((unsigned)(X) >> 24) & 0x0fffffff)) \ - + (unsigned)(Y)) + ((((EMACS_UINT) (X) << 4) + ((EMACS_UINT) (X) >> (BITS_PER_EMACS_INT - 4))) \ + + (EMACS_UINT) (Y)) +/* Hash X, returning a value that fits into a Lisp integer. */ +#define SXHASH_REDUCE(X) \ + ((((X) ^ (X) >> (BITS_PER_EMACS_INT - FIXNUM_BITS))) & INTMASK) /* Return a hash for string PTR which has length LEN. The hash code returned is guaranteed to fit in a Lisp integer. */ -static unsigned -sxhash_string (unsigned char *ptr, int len) +static EMACS_UINT +sxhash_string (unsigned char *ptr, EMACS_INT len) { unsigned char *p = ptr; unsigned char *end = p + len; unsigned char c; - unsigned hash = 0; + EMACS_UINT hash = 0; while (p != end) { c = *p++; if (c >= 0140) c -= 40; - hash = ((hash << 4) + (hash >> 28) + c); + hash = SXHASH_COMBINE (hash, c); } - return hash & INTMASK; + return SXHASH_REDUCE (hash); } +/* Return a hash for the floating point value VAL. */ + +static EMACS_INT +sxhash_float (double val) +{ + EMACS_UINT hash = 0; + enum { + WORDS_PER_DOUBLE = (sizeof val / sizeof hash + + (sizeof val % sizeof hash != 0)) + }; + union { + double val; + EMACS_UINT word[WORDS_PER_DOUBLE]; + } u; + int i; + u.val = val; + memset (&u.val + 1, 0, sizeof u - sizeof u.val); + for (i = 0; i < WORDS_PER_DOUBLE; i++) + hash = SXHASH_COMBINE (hash, u.word[i]); + return SXHASH_REDUCE (hash); +} /* Return a hash for list LIST. DEPTH is the current depth in the list. We don't recurse deeper than SXHASH_MAX_DEPTH in it. */ -static unsigned +static EMACS_UINT sxhash_list (Lisp_Object list, int depth) { - unsigned hash = 0; + EMACS_UINT hash = 0; int i; if (depth < SXHASH_MAX_DEPTH) @@ -4111,63 +4143,62 @@ sxhash_list (Lisp_Object list, int depth) CONSP (list) && i < SXHASH_MAX_LEN; list = XCDR (list), ++i) { - unsigned hash2 = sxhash (XCAR (list), depth + 1); + EMACS_UINT hash2 = sxhash (XCAR (list), depth + 1); hash = SXHASH_COMBINE (hash, hash2); } if (!NILP (list)) { - unsigned hash2 = sxhash (list, depth + 1); + EMACS_UINT hash2 = sxhash (list, depth + 1); hash = SXHASH_COMBINE (hash, hash2); } - return hash; + return SXHASH_REDUCE (hash); } /* Return a hash for vector VECTOR. DEPTH is the current depth in the Lisp structure. */ -static unsigned +static EMACS_UINT sxhash_vector (Lisp_Object vec, int depth) { - unsigned hash = ASIZE (vec); + EMACS_UINT hash = ASIZE (vec); int i, n; n = min (SXHASH_MAX_LEN, ASIZE (vec)); for (i = 0; i < n; ++i) { - unsigned hash2 = sxhash (AREF (vec, i), depth + 1); + EMACS_UINT hash2 = sxhash (AREF (vec, i), depth + 1); hash = SXHASH_COMBINE (hash, hash2); } - return hash; + return SXHASH_REDUCE (hash); } - /* Return a hash for bool-vector VECTOR. */ -static unsigned +static EMACS_UINT sxhash_bool_vector (Lisp_Object vec) { - unsigned hash = XBOOL_VECTOR (vec)->size; + EMACS_UINT hash = XBOOL_VECTOR (vec)->size; int i, n; n = min (SXHASH_MAX_LEN, XBOOL_VECTOR (vec)->header.size); for (i = 0; i < n; ++i) hash = SXHASH_COMBINE (hash, XBOOL_VECTOR (vec)->data[i]); - return hash; + return SXHASH_REDUCE (hash); } /* Return a hash code for OBJ. DEPTH is the current depth in the Lisp structure. Value is an unsigned integer clipped to INTMASK. */ -unsigned +EMACS_UINT sxhash (Lisp_Object obj, int depth) { - unsigned hash; + EMACS_UINT hash; if (depth > SXHASH_MAX_DEPTH) return 0; @@ -4211,20 +4242,14 @@ sxhash (Lisp_Object obj, int depth) break; case Lisp_Float: - { - double val = XFLOAT_DATA (obj); - unsigned char *p = (unsigned char *) &val; - size_t i; - for (hash = 0, i = 0; i < sizeof val; i++) - hash = SXHASH_COMBINE (hash, p[i]); - break; - } + hash = sxhash_float (XFLOAT_DATA (obj)); + break; default: abort (); } - return hash & INTMASK; + return hash; } @@ -4238,7 +4263,7 @@ DEFUN ("sxhash", Fsxhash, Ssxhash, 1, 1, 0, doc: /* Compute a hash code for OBJ and return it as integer. */) (Lisp_Object obj) { - unsigned hash = sxhash (obj, 0); + EMACS_UINT hash = sxhash (obj, 0); return make_number (hash); } @@ -4315,17 +4340,16 @@ usage: (make-hash-table &rest KEYWORD-ARGS) */) /* Look for `:rehash-size SIZE'. */ i = get_key_arg (QCrehash_size, nargs, args, used); rehash_size = i ? args[i] : make_float (DEFAULT_REHASH_SIZE); - if (!NUMBERP (rehash_size) - || (INTEGERP (rehash_size) && XINT (rehash_size) <= 0) - || XFLOATINT (rehash_size) <= 1.0) + if (! ((INTEGERP (rehash_size) && 0 < XINT (rehash_size)) + || (FLOATP (rehash_size) && 1 < XFLOAT_DATA (rehash_size)))) signal_error ("Invalid hash table rehash size", rehash_size); /* Look for `:rehash-threshold THRESHOLD'. */ i = get_key_arg (QCrehash_threshold, nargs, args, used); rehash_threshold = i ? args[i] : make_float (DEFAULT_REHASH_THRESHOLD); - if (!FLOATP (rehash_threshold) - || XFLOATINT (rehash_threshold) <= 0.0 - || XFLOATINT (rehash_threshold) > 1.0) + if (! (FLOATP (rehash_threshold) + && 0 < XFLOAT_DATA (rehash_threshold) + && XFLOAT_DATA (rehash_threshold) <= 1)) signal_error ("Invalid hash table rehash threshold", rehash_threshold); /* Look for `:weakness WEAK'. */ @@ -4437,7 +4461,7 @@ If KEY is not found, return DFLT which defaults to nil. */) (Lisp_Object key, Lisp_Object table, Lisp_Object dflt) { struct Lisp_Hash_Table *h = check_hash_table (table); - int i = hash_lookup (h, key, NULL); + EMACS_INT i = hash_lookup (h, key, NULL); return i >= 0 ? HASH_VALUE (h, i) : dflt; } @@ -4449,8 +4473,8 @@ VALUE. */) (Lisp_Object key, Lisp_Object value, Lisp_Object table) { struct Lisp_Hash_Table *h = check_hash_table (table); - int i; - unsigned hash; + EMACS_INT i; + EMACS_UINT hash; i = hash_lookup (h, key, &hash); if (i >= 0) @@ -4479,7 +4503,7 @@ FUNCTION is called with two arguments, KEY and VALUE. */) { struct Lisp_Hash_Table *h = check_hash_table (table); Lisp_Object args[3]; - int i; + EMACS_INT i; for (i = 0; i < HASH_TABLE_SIZE (h); ++i) if (!NILP (HASH_HASH (h, i))) diff --git a/src/image.c b/src/image.c index 0f269f46492..26542bf27e7 100644 --- a/src/image.c +++ b/src/image.c @@ -982,7 +982,6 @@ or omitted means use the selected frame. */) Image type independent image structures ***********************************************************************/ -static struct image *make_image (Lisp_Object spec, unsigned hash); static void free_image (struct frame *f, struct image *img); static int check_image_size (struct frame *f, int width, int height); @@ -991,7 +990,7 @@ static int check_image_size (struct frame *f, int width, int height); SPEC. SPEC has a hash value of HASH. */ static struct image * -make_image (Lisp_Object spec, unsigned int hash) +make_image (Lisp_Object spec, EMACS_UINT hash) { struct image *img = (struct image *) xmalloc (sizeof *img); Lisp_Object file = image_spec_value (spec, QCfile, NULL); @@ -1388,7 +1387,6 @@ x_alloc_image_color (struct frame *f, struct image *img, Lisp_Object color_name, Image Cache ***********************************************************************/ -static struct image *search_image_cache (struct frame *, Lisp_Object, unsigned); static void cache_image (struct frame *f, struct image *img); static void postprocess_image (struct frame *, struct image *); @@ -1414,7 +1412,7 @@ make_image_cache (void) /* Find an image matching SPEC in the cache, and return it. If no image is found, return NULL. */ static struct image * -search_image_cache (struct frame *f, Lisp_Object spec, unsigned int hash) +search_image_cache (struct frame *f, Lisp_Object spec, EMACS_UINT hash) { struct image *img; struct image_cache *c = FRAME_IMAGE_CACHE (f); @@ -1714,7 +1712,7 @@ int lookup_image (struct frame *f, Lisp_Object spec) { struct image *img; - unsigned hash; + EMACS_UINT hash; EMACS_TIME now; /* F must be a window-system frame, and SPEC must be a valid image @@ -3751,7 +3749,7 @@ xpm_put_color_table_h (Lisp_Object color_table, Lisp_Object color) { struct Lisp_Hash_Table *table = XHASH_TABLE (color_table); - unsigned hash_code; + EMACS_UINT hash_code; Lisp_Object chars = make_unibyte_string (chars_start, chars_len); hash_lookup (table, chars, &hash_code); diff --git a/src/lisp.h b/src/lisp.h index 8a504e8eb86..6e61d0b8bd3 100644 --- a/src/lisp.h +++ b/src/lisp.h @@ -525,23 +525,21 @@ extern Lisp_Object make_number (EMACS_INT); #define EQ(x, y) (XHASH (x) == XHASH (y)) -/* Largest and smallest representable fixnum values. These are the C - values. */ - +/* Number of bits in a fixnum, including the sign bit. */ #ifdef USE_2_TAGS_FOR_INTS -# define MOST_NEGATIVE_FIXNUM - ((EMACS_INT) 1 << VALBITS) -# define MOST_POSITIVE_FIXNUM (((EMACS_INT) 1 << VALBITS) - 1) -/* Mask indicating the significant bits of a Lisp_Int. - I.e. (x & INTMASK) == XUINT (make_number (x)). */ -# define INTMASK ((((EMACS_INT) 1) << (VALBITS + 1)) - 1) +# define FIXNUM_BITS (VALBITS + 1) #else -# define MOST_NEGATIVE_FIXNUM - ((EMACS_INT) 1 << (VALBITS - 1)) -# define MOST_POSITIVE_FIXNUM (((EMACS_INT) 1 << (VALBITS - 1)) - 1) -/* Mask indicating the significant bits of a Lisp_Int. - I.e. (x & INTMASK) == XUINT (make_number (x)). */ -# define INTMASK ((((EMACS_INT) 1) << VALBITS) - 1) +# define FIXNUM_BITS VALBITS #endif +/* Mask indicating the significant bits of a fixnum. */ +#define INTMASK (((EMACS_INT) 1 << FIXNUM_BITS) - 1) + +/* Largest and smallest representable fixnum values. These are the C + values. */ +#define MOST_POSITIVE_FIXNUM (INTMASK / 2) +#define MOST_NEGATIVE_FIXNUM (-1 - MOST_POSITIVE_FIXNUM) + /* Value is non-zero if I doesn't fit into a Lisp fixnum. It is written this way so that it also works if I is of unsigned type or if I is a NaN. */ @@ -1179,7 +1177,7 @@ struct Lisp_Hash_Table a special way (e.g. because of weakness). */ /* Number of key/value entries in the table. */ - unsigned int count; + EMACS_INT count; /* Vector of keys and values. The key of item I is found at index 2 * I, the value is found at index 2 * I + 1. @@ -1191,11 +1189,12 @@ struct Lisp_Hash_Table struct Lisp_Hash_Table *next_weak; /* C function to compare two keys. */ - int (* cmpfn) (struct Lisp_Hash_Table *, Lisp_Object, - unsigned, Lisp_Object, unsigned); + int (*cmpfn) (struct Lisp_Hash_Table *, + Lisp_Object, EMACS_UINT, + Lisp_Object, EMACS_UINT); /* C function to compute hash code. */ - unsigned (* hashfn) (struct Lisp_Hash_Table *, Lisp_Object); + EMACS_UINT (*hashfn) (struct Lisp_Hash_Table *, Lisp_Object); }; @@ -2093,7 +2092,7 @@ extern Lisp_Object Vascii_canon_table; /* Number of bytes of structure consed since last GC. */ -extern int consing_since_gc; +extern EMACS_INT consing_since_gc; extern EMACS_INT gc_relative_threshold; @@ -2468,19 +2467,19 @@ extern void syms_of_syntax (void); /* Defined in fns.c */ extern Lisp_Object QCrehash_size, QCrehash_threshold; -extern int next_almost_prime (int); -extern Lisp_Object larger_vector (Lisp_Object, int, Lisp_Object); +extern EMACS_INT next_almost_prime (EMACS_INT); +extern Lisp_Object larger_vector (Lisp_Object, EMACS_INT, Lisp_Object); extern void sweep_weak_hash_tables (void); extern Lisp_Object Qcursor_in_echo_area; extern Lisp_Object Qstring_lessp; extern Lisp_Object QCsize, QCtest, QCweakness, Qequal, Qeq, Qeql; -unsigned sxhash (Lisp_Object, int); +EMACS_UINT sxhash (Lisp_Object, int); Lisp_Object make_hash_table (Lisp_Object, Lisp_Object, Lisp_Object, Lisp_Object, Lisp_Object, Lisp_Object, Lisp_Object); -int hash_lookup (struct Lisp_Hash_Table *, Lisp_Object, unsigned *); -int hash_put (struct Lisp_Hash_Table *, Lisp_Object, Lisp_Object, - unsigned); +EMACS_INT hash_lookup (struct Lisp_Hash_Table *, Lisp_Object, EMACS_UINT *); +EMACS_INT hash_put (struct Lisp_Hash_Table *, Lisp_Object, Lisp_Object, + EMACS_UINT); void init_weak_hash_tables (void); extern void init_fns (void); EXFUN (Fmake_hash_table, MANY); diff --git a/src/minibuf.c b/src/minibuf.c index 4658b05e91d..39831e73b98 100644 --- a/src/minibuf.c +++ b/src/minibuf.c @@ -1209,7 +1209,7 @@ is used to further constrain the set of candidates. */) && (!SYMBOLP (XCAR (collection)) || NILP (XCAR (collection))))) ? list_table : function_table)); - int idx = 0, obsize = 0; + EMACS_INT idx = 0, obsize = 0; int matchcount = 0; int bindcount = -1; Lisp_Object bucket, zero, end, tem; @@ -1474,7 +1474,7 @@ with a space are ignored unless STRING itself starts with a space. */) : NILP (collection) || (CONSP (collection) && (!SYMBOLP (XCAR (collection)) || NILP (XCAR (collection)))); - int idx = 0, obsize = 0; + EMACS_INT idx = 0, obsize = 0; int bindcount = -1; Lisp_Object bucket, tem, zero; struct gcpro gcpro1, gcpro2, gcpro3, gcpro4; @@ -1770,7 +1770,7 @@ the values STRING, PREDICATE and `lambda'. */) (Lisp_Object string, Lisp_Object collection, Lisp_Object predicate) { Lisp_Object regexps, tail, tem = Qnil; - int i = 0; + EMACS_INT i = 0; CHECK_STRING (string); diff --git a/src/print.c b/src/print.c index 20c3e8ae526..803e3a17214 100644 --- a/src/print.c +++ b/src/print.c @@ -1082,7 +1082,7 @@ print (Lisp_Object obj, register Lisp_Object printcharfun, int escapeflag) Maybe a better way to do that is to copy elements to a new hash table. */ struct Lisp_Hash_Table *h = XHASH_TABLE (Vprint_number_table); - int i; + EMACS_INT i; for (i = 0; i < HASH_TABLE_SIZE (h); ++i) if (!NILP (HASH_HASH (h, i)) |